Difference between revisions of "1964 IMO Problems/Problem 1"

Latest revision as of 18:20, 22 August 2024

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$ .

Video Solution

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

@@ Line 3: / Line 3: @@
 '''(b)''' Prove that there is no positive integer <math>n</math> for which <math>2^n+1</math> is divisible by <math>7</math>.
+== Video Solution ==
+https://youtu.be/rap6C3ks29s
 == Solution 1 ==

1964 IMO (Problems) • Resources
Preceded by First question	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 2
All IMO Problems and Solutions

Page

Toolbox

Search