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

(Created page with '== Problem == (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</mat…')
 
(Solution)
Line 5: Line 5:
  
 
== Solution ==
 
== Solution ==
 +
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.
 +
 +
(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>.

Revision as of 19:29, 15 July 2009

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

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

Invalid username
Login to AoPS