Kvant Math Problem 62

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m20s
Source on kvant.digital

Problem

Prove that for any odd number $a$ there exists a natural number $b$ such that $2^b-1$ is divisible by $a$.

Exploration

Consider small odd numbers to test the claim. For $a=1$, any $b$ works because $2^b-1$ is divisible by $1$. For $a=3$, $2^2-1=3$ is divisible by $3$, so $b=2$ works. For $a=5$, $2^4-1=15$ is divisible by $5$, giving $b=4$. For $a=7$, $2^3-1=7$ works. For $a=9$, $2^6-1=63$ is divisible by $9$. Computing these suggests that for each odd $a$, there exists some exponent $b$ with $2^b \equiv 1 \pmod a$.

Attempting to falsify the conjecture, one might consider $a$ a large odd number, possibly composite. Since $2$ is coprime with any odd $a$, the multiplicative group modulo $a$ has finite order $\phi(a)$, where $\phi$ is Euler's totient function. Therefore, the powers of $2$ modulo $a$ are periodic, suggesting that some power will be congruent to $1$ modulo $a$. The critical step is rigorously justifying that this periodicity always guarantees a positive integer solution, particularly when $a$ is composite.

The most likely source of error is assuming the group-theoretic argument implicitly without explicitly verifying that the period divides $\phi(a)$ and thus that a finite $b$ exists.

Problem Understanding

The problem asks to prove that for every odd natural number $a$, there exists a natural number $b$ such that $2^b-1$ is divisible by $a$, equivalently, $2^b \equiv 1 \pmod a$. This is a Type B problem since the statement is an absolute claim to prove for all odd $a$. The core difficulty lies in establishing the existence of an exponent $b$ for arbitrary odd $a$, including composite numbers, without assuming any results beyond elementary number theory.

The underlying principle is that $2$ is coprime to any odd $a$, so repeated multiplication by $2$ modulo $a$ must eventually return to $1$ due to the finiteness of residues modulo $a$. This finiteness suggests a cyclic behavior, which is the crucial insight.

Proof Architecture

Lemma 1. If $a$ is odd, then $\gcd(2,a)=1$. This is immediate from the parity of $a$.

Lemma 2. If $\gcd(2,a)=1$, then the sequence $2^1, 2^2, 2^3, \dots$ modulo $a$ is eventually periodic. This follows from the Pigeonhole Principle, since there are only $a$ distinct residues modulo $a$.

Lemma 3. In any finite sequence of positive integers taken modulo $a$, if $\gcd(2,a)=1$, some power must be congruent to $1$ modulo $a$. This is a consequence of Lemma 2: the first repeated residue in the periodic sequence implies that a difference of exponents gives $2^b \equiv 1 \pmod a$.

The hardest step is Lemma 3, ensuring that the periodicity indeed produces $1$ and not just some other repeated residue.

Solution

Let $a$ be any odd natural number. Then $\gcd(2,a)=1$ because $a$ is not divisible by $2$. Consider the sequence of powers of $2$ modulo $a$: $2^1, 2^2, 2^3, \dots$. Since there are only $a$ distinct residues modulo $a$, by the Pigeonhole Principle there exist indices $i<j$ such that $2^i \equiv 2^j \pmod a$. Subtracting these congruences gives $2^i(2^{j-i}-1) \equiv 0 \pmod a$. Because $\gcd(2^i,a)=1$, we may divide both sides by $2^i$ to obtain $2^{j-i}-1 \equiv 0 \pmod a$. Setting $b=j-i$ gives a natural number satisfying $2^b-1$ divisible by $a$.

Every step has been justified: $\gcd(2,a)=1$ ensures divisibility cancellation is valid, the Pigeonhole Principle guarantees repetition in the finite residue set, and the subtraction produces exactly the required form. This completes the proof.

∎

Verification of Key Steps

In Lemma 3, the critical step is dividing by $2^i$ modulo $a$. Since $a$ is odd, $2^i$ is coprime to $a$, so this division is valid. Testing with small odd numbers confirms this: for $a=5$, $2^1=2$, $2^2=4$, $2^3=3$, $2^4=1$; here, $i=0$, $j=4$ yields $2^4-1=15$ divisible by $5$. For composite numbers like $a=9$, $2^1=2$, $2^2=4$, $2^3=8$, $2^4=7$, $2^5=5$, $2^6=1$; again, $2^6-1=63$ divisible by $9$. These confirm the argument.

Applying the Pigeonhole Principle for larger odd numbers also produces repeated residues eventually, and subtracting gives a multiple of $a$, ensuring $2^b-1$ is divisible by $a$. No counterexamples appear, so the argument is robust.

Alternative Approaches

An alternative approach uses Euler's theorem: for any $a$ with $\gcd(2,a)=1$, $2^{\phi(a)} \equiv 1 \pmod a$, where $\phi(a)$ is Euler's totient function. Then $b=\phi(a)$ immediately satisfies $2^b-1 \equiv 0 \pmod a$. This approach is more direct but requires Euler's theorem as a known result. The chosen approach avoids invoking Euler's theorem explicitly and relies only on elementary divisibility and the Pigeonhole Principle, making it more accessible in a school-level setting.