IMO 1964 Problem 1

Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 7m13s

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

Exploration

The problem concerns divisibility of powers of $2$ by $7$, so the natural setting is arithmetic modulo $7$. Since divisibility by $7$ is equivalent to congruence to $0$ modulo $7$, the task reduces to understanding the residue sequence $2^n \bmod 7$.

Computing small powers gives $2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 \equiv 8 \equiv 1 \pmod{7}$. Once $1$ appears, the sequence becomes periodic with period $3$, because multiplication by $2$ cycles through the residues $2,4,1$ repeatedly. This suggests that $2^n \equiv 1 \pmod{7}$ precisely when $n$ is a multiple of $3$.

For the second part, we consider $2^n + 1 \equiv 0 \pmod{7}$, or equivalently $2^n \equiv 6 \pmod{7}$. In the observed cycle ${1,2,4}$, the residue $6$ never appears, so one expects impossibility.

The main difficulty is to justify rigorously that no other residues occur beyond the cycle already observed, and that periodicity is complete.

Problem Understanding

This is a Type A problem, a classification problem asking for all positive integers $n$ satisfying a divisibility condition.

We must determine all $n$ such that $7 \mid (2^n - 1)$, and also prove that $7 \nmid (2^n + 1)$ for any positive integer $n$.

The structure of powers modulo $7$ is central. The key idea is that modular exponentiation produces a repeating cycle because there are only finitely many residues modulo $7$. The expected result is that $2^n \equiv 1 \pmod{7}$ exactly when $n$ is divisible by $3$, and that $2^n \equiv -1 \pmod{7}$ has no solution because $-1 \equiv 6 \pmod{7}$ is not in the cycle.

Thus the answer for part (a) should be all multiples of $3$, and part (b) should assert nonexistence.

Proof Architecture

Lemma 1 states that the sequence $2^n \bmod 7$ is periodic with period dividing $3$ because $2^3 \equiv 1 \pmod{7}$, and consequently $2^{n+3} \equiv 2^n \pmod{7}$. This follows from direct factorization $2^{n+3} = 2^n \cdot 2^3$.

Lemma 2 states that $2^n \equiv 1 \pmod{7}$ if and only if $3 \mid n$. The forward direction uses the minimality of the multiplicative order of $2$ modulo $7$, and the reverse direction follows from Lemma 1.

Lemma 3 states that $2^n \bmod 7$ can only take values in ${1,2,4}$ for all $n \ge 1$, established by direct computation of the cycle and induction using Lemma 1.

Lemma 4 states that $2^n \not\equiv 6 \pmod{7}$ for all $n$, since $6 \notin {1,2,4}$.

The most delicate step is Lemma 2, since it requires ruling out smaller positive exponents producing $1$ modulo $7$.

Solution

Lemma 1

For all positive integers $n$, one has $2^{n+3} \equiv 2^n \pmod{7}$.

Since $2^{n+3} = 2^n \cdot 2^3$, and $2^3 = 8$, it follows that $2^3 \equiv 1 \pmod{7}$ because $8 = 7 + 1$. Therefore $2^{n+3} \equiv 2^n \cdot 1 \equiv 2^n \pmod{7}$.

This establishes that multiplication by $2^3$ does not change residues modulo $7$, so shifting the exponent by $3$ preserves congruence classes.

Lemma 2

For all positive integers $n$, $2^n \equiv 1 \pmod{7}$ holds if and only if $3 \mid n$.

First, suppose $n = 3k$ for some positive integer $k$. Then $2^n = 2^{3k} = (2^3)^k$. Since $2^3 \equiv 1 \pmod{7}$, it follows that $(2^3)^k \equiv 1^k \equiv 1 \pmod{7}$.

Conversely, suppose $2^n \equiv 1 \pmod{7}$. By Lemma 1, reducing exponents modulo $3$ preserves residues, so each integer $n$ yields one of the residues obtained from $2^1,2^2,2^3$. Direct computation gives $2^1 \equiv 2 \pmod{7}$, $2^2 \equiv 4 \pmod{7}$, and $2^3 \equiv 1 \pmod{7}$. The only exponent among $1,2,3$ producing residue $1$ is $3$. Since Lemma 1 shows the sequence repeats every $3$ steps and no earlier exponent produces $1$, it follows that $n$ must lie in the residue class of $3$ modulo $3$, hence $3 \mid n$.

This establishes that $2^n \equiv 1 \pmod{7}$ occurs exactly at multiples of $3$.

Lemma 3

For every positive integer $n$, $2^n \bmod 7$ belongs to ${1,2,4}$.

Direct computation yields $2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 \equiv 1$. By Lemma 1, multiplying any exponent by $2^3$ preserves the residue, so the sequence repeats every three steps. Hence all powers of $2$ modulo $7$ are among the residues already observed in one complete cycle, namely $1,2,4$.

This certifies that no other residue can occur in the sequence of powers of $2$ modulo $7$.

Lemma 4

For every positive integer $n$, $2^n \not\equiv 6 \pmod{7}$.

From Lemma 3, every residue of $2^n$ modulo $7$ lies in ${1,2,4}$, and since $6 \notin {1,2,4}$, no power of $2$ is congruent to $6$ modulo $7$.

This eliminates the possibility of solving $2^n \equiv -1 \pmod{7}$.

Part (a)

From Lemma 2, $2^n - 1$ is divisible by $7$ if and only if $2^n \equiv 1 \pmod{7}$, which holds exactly when $3 \mid n$.

Hence all positive integers $n$ satisfying the condition are precisely the multiples of $3$.

Part (b)

The condition $7 \mid (2^n + 1)$ is equivalent to $2^n \equiv 6 \pmod{7}$. Lemma 4 shows that no such congruence is possible for any positive integer $n$.

This completes the proof. ∎

Verification of Key Steps

The most delicate point is the identification of the full residue cycle. Recomputing independently, one finds $2 \equiv 2 \pmod{7}$, $2^2 \equiv 4 \pmod{7}$, and $2^3 \equiv 8 \equiv 1 \pmod{7}$. Multiplying again gives $2^4 \equiv 2$, $2^5 \equiv 4$, $2^6 \equiv 1$, confirming that no new residues appear beyond ${1,2,4}$.

Another critical step is ruling out $2^n \equiv 1 \pmod{7}$ for any $n$ not divisible by $3$. Direct inspection of the cycle shows that only positions $n \equiv 0 \pmod{3}$ yield residue $1$, and no shorter repetition exists since $2^1 \not\equiv 1$ and $2^2 \not\equiv 1$.

Finally, the exclusion of $6$ is verified directly against the complete residue set, which contains exactly three elements and omits $6$ entirely.

Alternative Approaches

A different approach uses Fermat’s little theorem, which states that $2^6 \equiv 1 \pmod{7}$. From this one can deduce periodicity with period dividing $6$, then refine the period to $3$ by computing $2^3 \equiv 1 \pmod{7}$. Another approach uses the multiplicative group $(\mathbb{Z}/7\mathbb{Z})^\times$, which is cyclic of order $6$, so $2$ must have order dividing $6$, and direct computation shows its order is $3$, yielding the same classification.