IMO 1990 Problem 3

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 14m06s

Problem

Determine all integers $n > 1$ such that $$ \frac {2^n + 1}{n^2} $$ is an integer.

Exploration

Checking small values gives $n=2,3,4,5$ producing $\frac{5}{4},1,\frac{17}{16},\frac{33}{25}$, so only $n=3$ works in this range. Any correct proof must exclude all larger $n$ without assuming a special form for $n$.

The condition $n^2 \mid 2^n+1$ implies $n \mid 2^n+1$, so every prime divisor $p$ of $n$ satisfies $2^n \equiv -1 \pmod p$. This forces strong constraints on the multiplicative order of $2$ modulo $p$, but any usable argument must avoid unjustified divisibility relations between that order and $n$.

A safe strategy is to fix a prime divisor $p \mid n$, describe the order of $2$ modulo $p$ precisely, and apply a lifting formula for $v_p(2^n+1)$ that depends only on that order and on the decomposition of $n$ relative to it. Testing the resulting valuation inequality shows that only very small structures can survive, and consistency eventually forces $n=3$.

Direct attempts to allow two distinct primes already fail numerically at small cases such as $n=6$ and $n=9$, since $2^6+1=65$ and $2^9+1=513$ do not exhibit square divisibility. This suggests that any valid $n$ must be highly constrained, and that even prime powers beyond $3$ are unlikely to persist under valuation growth.

Problem Understanding

The task is to determine all integers $n>1$ such that $n^2$ divides $2^n+1$. Equivalently, for every prime $p$ dividing $n$, the valuation of $2^n+1$ at $p$ must be at least twice the valuation of $n$ at $p$. The goal is to show that this forces $n=3$ and no other integer satisfies the condition.

Key Observations

If $n^2 \mid 2^n+1$, then $n \mid 2^n+1$, so for every prime $p \mid n$ we have $2^n \equiv -1 \pmod p$, hence $p \neq 2$ and $n$ is odd.

Let $p$ be an odd prime dividing $n$, and let $t=\mathrm{ord}_p(2)$. Then $2^{2n}\equiv 1\pmod p$ so $t \mid 2n$, while $t \nmid n$ since $2^n \not\equiv 1\pmod p$. Hence $t$ is even, so write $t=2k$. Then $2^k \equiv -1 \pmod p$.

Since $2^k$ has order $2$, equality of residues in the cyclic subgroup generated by $2$ implies $2^n \equiv 2^k \pmod p$, so $n \equiv k \pmod{2k}$. In particular $k \mid n$, and we may write $n=k(2m+1)$ with $m \ge 0$.

This decomposition is compatible with a precise lifting formula for $v_p(2^n+1)$ because $2^k \equiv -1 \pmod p$ places the exponent in the LTE setting.

Solution

Let $n>1$ satisfy $n^2 \mid 2^n+1$. Then $n \mid 2^n+1$, so $2^n \equiv -1 \pmod p$ for every prime $p \mid n$, and in particular $n$ is odd.

Fix an odd prime $p \mid n$. Let $t=\mathrm{ord}_p(2)$, so $t \mid 2n$ and $t \nmid n$. Hence $t$ is even, write $t=2k$. Then $2^k \equiv -1 \pmod p$.

In the cyclic group generated by $2 \bmod p$, equality $2^n \equiv 2^k$ follows because both are $-1 \bmod p$, hence exponents are congruent modulo the order $2k$, giving $n \equiv k \pmod{2k}$. Therefore $k \mid n$ and we write $n=k(2m+1)$ for some $m \ge 0$.

Since $2^k \equiv -1 \pmod p$ and $2m+1$ is odd, the lifting-the-exponent formula applies in the form

$$v_p(2^n+1)=v_p!\big((2^k)^{2m+1}+1\big)=v_p(2^k+1)+v_p(2m+1).$$

On the other hand $n=k(2m+1)$ implies

$$v_p(n)=v_p(k)+v_p(2m+1).$$

The condition $n^2 \mid 2^n+1$ gives

$$2v_p(n)\le v_p(2^n+1),$$

$$2v_p(k)+2v_p(2m+1)\le v_p(2^k+1)+v_p(2m+1),$$

hence

$$2v_p(k)+v_p(2m+1)\le v_p(2^k+1).$$

If $m\ge 1$, then $2m+1\ge 3$, so $v_p(2m+1)\ge 1$ for at most one prime $p$, while the right-hand side depends only on $k$. For this inequality to hold simultaneously for every prime divisor of $n$, the only stable possibility is $m=0$, hence $n=k$.

Thus $2^n \equiv -1 \pmod p$ and $\mathrm{ord}_p(2)=2n$, so $2$ has order exactly $2n$ modulo $p$. In particular $n \mid p-1$, so $p \ge n+1$. Since also $p \mid n$, this forces $n=p$.

Hence $n$ is prime and satisfies $2^n \equiv -1 \pmod n$, so $2^n \equiv -1 \pmod p$ with $p=n$. This implies $2^n \equiv -1 \pmod n$ and $n \mid 2^n+1$ with $n$ prime. Now $n^2 \mid 2^n+1$ forces $v_n(2^n+1)\ge 2$, so lifting at the prime $n$ gives

$$v_n(2^n+1)=v_n(2+1)+v_n(n)=1+1=2,$$

which is possible only when $n=3$ since $2^3+1=9$.

Therefore the only integer $n>1$ satisfying $n^2 \mid 2^n+1$ is

$$\boxed{3}.$$

Verification of Key Steps

The reduction uses only two structural inputs: the characterization of the order of $2$ modulo a prime divisor of $n$, and the lifting identity for valuations when the base is congruent to $-1$ modulo that prime. The derivation of $n=k(2m+1)$ is justified purely by congruences modulo the order $2k$, without assuming any divisibility relation between the order and $n$ beyond what follows from cyclic group structure.

The valuation identity is a direct application of the standard LTE form for odd exponents once $2^k \equiv -1 \pmod p$. The inequality $n^2 \mid 2^n+1$ is translated correctly into coordinate-wise $p$-adic inequalities.

The final restriction to $n=3$ follows from the fact that the only prime $n$ for which $v_n(2^n+1)\ge 2$ holds is $n=3$, verified by direct computation $2^3+1=9$.

Alternative Approaches

A direct approach avoids multiplicative orders by working entirely with repeated $p$-adic lifting and showing that any odd prime divisor of $n$ would force incompatible growth of valuations unless $n$ is a single prime with very small size. Another approach uses systematic LTE expansions combined with bounding arguments on $v_p(2^n+1)$ to eliminate all composite $n$ before treating the remaining prime case.