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 see that <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.
 
  
(a) From the statement above, only <math>n</math> divisible by <math>3</math> work.
+
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

Problem

(a) Find all positive integers $n$ for which $2^n-1$ is divisible by $7$.

(b) Prove that there is no positive integer $n$ for which $2^n+1$ is divisible by $7$.

Solution 1

We claim $2^n$ is equivalent to $2, 4,$ and $1$ $\pmod{7}$ for $n$ congruent to $1$, $2$, and $0$ $\pmod{3}$, respectively.

(a) From the statement above, only $n$ divisible by $3$ will work.

(b) Again from the statement above, $2^n$ can never be congruent to $-1$ $\pmod{7}$, so there are no solutions for $n$.


Solution 1.1

This solution is clearer and easier to understand.

(1) Since we know that $2^n-1$ is congruent to 0 (mod 7), we know that $2^n$ is congruent to 8 mod 7, which means $2^n$ is congruent to 1 mod 7.

Experimenting with the residue of $2^n$ mod 7:

$n$=1: 2

$n$=2: 4

$n$=3: 1 (this is because when $2^n$ is doubled to $2*2^n$, the residue doubles too, but $4*2=8$ is congruent to 1 (mod 7).

$n$=4: 2

$n$=5: 4

$n$=6: 1

Through induction, we easily show that this is true since the residue doubles every time you double $2^n$.

So, the residue of $2^n$ mod 7 cycles in 2, 4, 1. Therefore, $n$ must be a multiple of 3. Proved.

(2) According to part (1), the residue of $2^n$ cycles in 2, 4, 1.

If $2^n+1$ is congruent to 0 mod 7, then $2^n$ must be congruent to 6 mod 7, but this is not possible due to how $2^n$ 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