Difference between revisions of "1964 IMO Problems/Problem 1"
Hastapasta (talk | contribs) m (→Solution) |
Hastapasta (talk | contribs) (→Solution) |
||
| Line 16: | Line 16: | ||
The solution is clearer and easier to understand. | 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. | (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: | Experimenting with the residue of <math>2^n</math> mod 7: | ||
| + | |||
n=1: 2 | n=1: 2 | ||
| + | |||
n=2: 4 | 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=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=4: 2 | ||
| + | |||
n=5: 4 | n=5: 4 | ||
| + | |||
n=6: 1 | n=6: 1 | ||
| + | |||
Through induction, we easy show that this is true since the residue doubles every time you double <math>2^n</math>. | 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. | 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. | + | |
| + | (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 | ~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:41, 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 | ||
