Difference between revisions of "1964 IMO Problems/Problem 1"
(→Solution) |
m (→Solution 1) |
||
(12 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | (a) Find all positive integers <math>n</math> for which <math>2^n-1</math> is divisible by <math>7</math>. | + | '''(a)''' Find all positive integers <math>n</math> for which <math>2^n-1</math> is divisible by <math>7</math>. |
− | (b) Prove that there is no positive integer <math>n</math> for which <math>2^n+1</math> is divisible by <math>7</math>. | + | '''(b)''' Prove that there is no positive integer <math>n</math> for which <math>2^n+1</math> is divisible by <math>7</math>. |
− | == Solution == | + | == Solution 1 == |
− | |||
− | + | We claim <math>2^n</math> is equivalent to <math>2, 4,</math> and <math>1</math> <math>\pmod{7}</math> for <math>n</math> congruent to <math>1</math>, <math>2</math>, and <math>0</math> <math>\pmod{3}</math>, respectively. | |
− | (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>. | + | '''(a)''' From the statement above, only <math>n</math> divisible by <math>3</math> will work. |
+ | |||
+ | '''(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 === | ||
+ | This 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: | ||
+ | |||
+ | <math>n</math>=1: 2 | ||
+ | |||
+ | <math>n</math>=2: 4 | ||
+ | |||
+ | <math>n</math>=3: 1 (this is because when <math>2^n</math> is doubled to <math>2*2^n</math>, the residue doubles too, but <math>4*2=8</math> is congruent to 1 (mod 7). | ||
+ | |||
+ | <math>n</math>=4: 2 | ||
+ | |||
+ | <math>n</math>=5: 4 | ||
+ | |||
+ | <math>n</math>=6: 1 | ||
+ | |||
+ | Through induction, we easily 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 == | ||
+ | {{IMO box|year=1964|before=First question|num-a=2}} |
Latest revision as of 01:08, 18 July 2023
Contents
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 1
We claim is equivalent to
and
for
congruent to
,
, and
, respectively.
(a) From the statement above, only divisible by
will work.
(b) Again from the statement above, can never be congruent to
, so there are no solutions for
.
Solution 1.1
This 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:
=1: 2
=2: 4
=3: 1 (this is because when
is doubled to
, the residue doubles too, but
is congruent to 1 (mod 7).
=4: 2
=5: 4
=6: 1
Through induction, we easily 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 |