Kvant Math Problem 672

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m33s
Source on kvant.digital

Problem

Let $a$ be a natural number such that $2^a-2$ is divisible by $a$ (for example, $a=3$). Define the sequence $(x_n)$ by the conditions $$x_1=a,\quad x_{k+1}=2^{x_k}-1$$. Prove that $2^{x_k}-2$ is divisible by $x_k$ for any $k$.

Walter Janous (Innsbruck, Austria)

Exploration

Let $f(n)=2^n-1$. The sequence is $x_{k+1}=f(x_k)$ with $x_1=a$ and the hypothesis $a\mid 2^a-2$, i.e. $2^a\equiv 2 \pmod a$.

The goal is to show that every iterate $x_k$ satisfies $x_k\mid 2^{x_k}-2$, meaning the same congruence is preserved under $f$.

The key difficulty is to connect a divisibility property involving $n$ with a new modulus $2^n-1$. A natural invariant to track is the multiplicative order of $2$ modulo the current term. The expression $2^n\equiv 1 \pmod{2^n-1}$ suggests that the order modulo $x_{k+1}$ divides $x_k$, which interacts well with the assumption that $x_k\mid 2^{x_k}-2$.

The central step is to show that if $2^n\equiv 1 \pmod{2^n-1}$ then the order of $2$ modulo $2^n-1$ divides $n$, and hence divides $2^n-2$ once the induction hypothesis is used.

Problem Understanding

This is a Type B problem: one must prove that every term $x_k$ of the recursively defined sequence satisfies $x_k\mid 2^{x_k}-2$, assuming the initial condition $a\mid 2^a-2$.

The structure is iterative: each term is $x_{k+1}=2^{x_k}-1$, so the statement must be shown to propagate through the transformation $n\mapsto 2^n-1$.

The core difficulty is to relate modular arithmetic at level $n$ to modular arithmetic at level $2^n-1$, and to find a property stable under this exponential recursion. The correct invariant is the multiplicative order of $2$.

Proof Architecture

The proof proceeds by induction on $k$.

The first lemma states that from $x_k\mid 2^{x_k}-2$ and $x_k$ odd, it follows that the multiplicative order of $2$ modulo $x_k$ divides $x_k$.

The second lemma establishes that if $m=2^n-1$, then $2^n\equiv 1\pmod m$, hence the order of $2$ modulo $m$ divides $n$.

The third lemma combines these facts to show that if $n\mid 2^n-2$, then $2^{2^n-1}-2$ is divisible by $2^n-1$.

The most delicate point is the transition from information modulo $n$ to a statement about the order modulo $2^n-1$, ensuring the divisibility condition is correctly transferred.

Solution

Let $x_1=a$ with $a\mid 2^a-2$. Define $x_{k+1}=2^{x_k}-1$.

First observe that $a\mid 2^a-2$ implies $a\mid 2(2^{a-1}-1)$. Since $2^a-2$ is even, $a$ is odd, hence $a\mid 2^{a-1}-1$, which yields

$2^{a-1}\equiv 1 \pmod a.$

Thus the multiplicative order of $2$ modulo $a$ divides $a-1$, and in particular divides $a$.

Now assume $n$ is a positive integer such that $n\mid 2^n-2$. Set $m=2^n-1$. Then

$2^n\equiv 1 \pmod m.$

Let $t$ be the multiplicative order of $2$ modulo $m$. The congruence $2^n\equiv 1\pmod m$ implies $t\mid n$.

Since $n\mid 2^n-2$, there exists an integer $k$ such that $2^n-2=kn$. From $t\mid n$ it follows that $t\mid kn$, hence

$t\mid 2^n-2.$

Therefore,

$2^{2^n-2}\equiv 1 \pmod m.$

Multiplying both sides by $2$ gives

$2^{2^n-1}\equiv 2 \pmod m,$

which is equivalent to

$2^{m}\equiv 2 \pmod m,$

so $m\mid 2^m-2$.

This shows that if $n$ satisfies the required divisibility property, then so does $2^n-1$. Since $x_1=a$ satisfies the property, induction yields that every $x_k$ satisfies

$x_k\mid 2^{x_k}-2.$

This completes the proof. ∎

Verification of Key Steps

The crucial transition is the identification of the order $t$ of $2$ modulo $m=2^n-1$. The congruence $2^n\equiv 1\pmod m$ ensures that $t\mid n$ by definition of order, since the order is the smallest positive exponent giving $1$.

The second delicate point is the implication $t\mid n$ and $n\mid 2^n-2$ implying $t\mid 2^n-2$. This follows directly from divisibility transitivity: writing $2^n-2=kn$ gives $2^n-2=k n$, hence any divisor of $n$ divides $2^n-2$.

The final step converting $2^{2^n-2}\equiv 1\pmod m$ into $2^{2^n-1}\equiv 2\pmod m$ is a direct multiplication by $2$ in modular arithmetic, valid because $m$ is odd and no divisibility issues arise.

Alternative Approaches

One can also frame the argument entirely in terms of multiplicative orders without explicit induction. The transformation $n\mapsto 2^n-1$ forces the order of $2$ modulo each term to divide the previous term, and the initial condition ensures compatibility with the required exponent. Another approach uses the theory of repunit-like numbers and properties of the group $(\mathbb{Z}/(2^n-1)\mathbb{Z})^\times$, but this ultimately reduces to the same order-based argument.