Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution)
m (→‎Solution 1.0)
Line 19: Line 19:
 
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
+
<math>n</math>=1: 2
  
−
n=2: 4
+
<math>n</math>=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).
+
<math>n</math>=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
+
<math>n</math>=4: 2
  
−
n=5: 4
+
<math>n</math>=5: 4
  
−
n=6: 1
+
<math>n</math>=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>.
Line 35: Line 35:
 
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*2^n</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

Revision as of 18:43, 7 January 2022

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

We see that $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$ 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: The 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^(n+1)$, the residue doubles too, but $4*2$ 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 $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*2^n$ 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1964_IMO_Problems/Problem_1&oldid=169506"