Difference between revisions of "1964 IMO Problems/Problem 1"
Hastapasta (talk | contribs) m (→Solution) |
|||
Line 11: | Line 11: | ||
'''(b)''' Again from the statement above, <math>2^n</math> can never be congruent to <math>-1</math> <math>\pmod{7}</math>, so there are no solutions for <math>n</math>. | '''(b)''' Again from the statement above, <math>2^n</math> can never be congruent to <math>-1</math> <math>\pmod{7}</math>, so there are no solutions for <math>n</math>. | ||
+ | |||
+ | |||
+ | Solution 1.1: | ||
+ | The solution is clearer and easier to understand. | ||
+ | (1) Since we know that <math>2^n-1</math> is congruent to 0 (mod 7), we know that <math>2^n</math> is congruent to 8 mod 7, which means <math>2^n</math> is congruent to 1 mod 7. | ||
+ | Experimenting with the residue of <math>2^n</math> mod 7: | ||
+ | n=1: 2 | ||
+ | n=2: 4 | ||
+ | n=3: 1 (this is because when <math>2^n</math> is doubled to <math>2^(n+1)</math>, the residue doubles too, but <math>4*2</math> is congruent to 1 (mod 7). | ||
+ | n=4: 2 | ||
+ | n=5: 4 | ||
+ | n=6: 1 | ||
+ | Through induction, we easy show that this is true since the residue doubles every time you double <math>2^n</math>. | ||
+ | So, the residue of <math>2^n</math> mod 7 cycles in 2, 4, 1. Therefore, <math>n</math> must be a multiple of 3. Proved. | ||
+ | (2) According to part (1), the residue of <math>2^n</math> cycles in 2, 4, 1. If <math>2^n+1</math> is congruent to 0 mod 7, then <math>2^n</math> must be congruent to 6 mod 7, but this is not possible due to how <math>2^n</math> mod 7 cycles. Therefore, there is no solution. Proved. | ||
+ | ~hastapasta | ||
== See Also == | == See Also == | ||
{{IMO box|year=1964|before=First question|num-a=2}} | {{IMO box|year=1964|before=First question|num-a=2}} |
Revision as of 19:40, 7 January 2022
Problem
(a) Find all positive integers for which
is divisible by
.
(b) Prove that there is no positive integer for which
is divisible by
.
Solution
We see that is equivalent to
and
for
congruent to
,
, and
, respectively.
(a) From the statement above, only divisible by
work.
(b) Again from the statement above, can never be congruent to
, so there are no solutions for
.
Solution 1.1:
The solution is clearer and easier to understand.
(1) Since we know that is congruent to 0 (mod 7), we know that
is congruent to 8 mod 7, which means
is congruent to 1 mod 7.
Experimenting with the residue of
mod 7:
n=1: 2
n=2: 4
n=3: 1 (this is because when
is doubled to
, the residue doubles too, but
is congruent to 1 (mod 7).
n=4: 2
n=5: 4
n=6: 1
Through induction, we easy show that this is true since the residue doubles every time you double
.
So, the residue of
mod 7 cycles in 2, 4, 1. Therefore,
must be a multiple of 3. Proved.
(2) According to part (1), the residue of
cycles in 2, 4, 1. If
is congruent to 0 mod 7, then
must be congruent to 6 mod 7, but this is not possible due to how
mod 7 cycles. Therefore, there is no solution. Proved.
~hastapasta
See Also
1964 IMO (Problems) • Resources | ||
Preceded by First question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |