IMO 1990 Problem 3: Lifting the Exponent and Fermat’s Little Theorem

Problem (IMO 1990, Problem 3). Determine all integers \(n > 1\) such that \(\dfrac{2^n+1}{n^2}\) is an integer.

The answer is \(n = 3\). Indeed \(\frac{2^3+1}{3^2} = 1\), and below we show that no other \(n\) works.

Step 1: the smallest prime factor of \(n\) is \(3\)

Since \(2^n + 1\) is odd, \(n\) is odd. Let \(a\) be the smallest prime dividing \(n\), so \(a \neq 2\).

Since \(a \mid 2^n+1\), also \(a \mid (2^n+1)(2^n-1) = 2^{2n}-1\). By Fermat’s little theorem, \(a \mid 2^{a-1}-1\). Therefore

\[a \mid 2^{\gcd(2n,\, a-1)}-1.\]

Every prime factor of \(a - 1\) is smaller than \(a\), so it cannot divide \(n\); and \(a - 1\) is even while \(n\) is odd. Hence \(\gcd(2n,\, a-1)=2\), and \(a \mid 2^2 - 1 = 3\), so \(a=3\).

Write \(n=3^x y\) with \(x \geq 1\) and \(3 \nmid y\).

Step 2: \(3\) divides \(n\) exactly once

Lifting-the-exponent lemma. Let \(p\) be an odd prime and \(a\), \(b\) integers with \(p \mid a+b\) but \(p \nmid a\) and \(p \nmid b\). Then for every odd positive integer \(n\),

\[v_p(a^n+b^n)=v_p(a+b)+v_p(n),\]

where \(v_p(m)\) is the exponent of \(p\) in the prime factorisation of \(m\).

With \(p=3\), \(a=2\), \(b=1\):

\[v_3(2^n+1)=v_3(3)+v_3(n) = 1 + x.\]

Since \(n^2 \mid 2^n+1\), we need \(v_3(n^2) \leq v_3(2^n+1)\), that is, \(2x \leq x+1\). So \(x \leq 1\), and therefore \(x=1\): \(n = 3y\) with \(3 \nmid y\).

Step 3: \(y = 1\)

Suppose \(y > 1\) and let \(q\) be the smallest prime factor of \(y\), so \(q \geq 5\). As in Step 1, \(q \mid 2^{\gcd(2n,\, q-1)}-1\). Every prime factor of \(q-1\) is smaller than \(q\), so the only one that can divide \(n = 3y\) is \(3\), and \(9 \nmid n\). Hence \(\gcd(n, q-1) \in \{1, 3\}\) and \(\gcd(2n, q-1) \in \{2, 6\}\), so

\[q \mid 2^6 - 1 = 63 = 3^2 \cdot 7 .\]

Since \(q \ge 5\), we get \(q=7\). But then \(7 \mid 2^n + 1\), i.e. \(2^n \equiv -1 \pmod 7\), which is impossible: the powers of \(2\) modulo \(7\) are only \(1, 2, 4\). This contradiction shows \(y = 1\).

Therefore \(n=3\) is the only solution. \(\blacksquare\)

Exercises

• Why is \(n\) odd?
• Why does \(a \mid 2^n+1\) imply \(a \mid 2^{2n}-1\)?
• Why does \(a \mid 2^{2n}-1\) and \(a \mid 2^{a-1}-1\) imply \(a \mid 2^{\gcd(2n,\, a-1)}-1\)?
• State the lifting-the-exponent lemma in full, including the case \(p = 2\) and the version for \(a^n - b^n\).
• Why can’t we simply conclude \(n=3^k\) after Step 1?

Credits

The solution is based on this Art of Problem Solving thread and this handout.

Changes on 25 October 2026

What was wrong. One step of the proof was invalid. It argued that \(2^n + 1 > n^2\) implies \(v_3(2^n+1) > v_3(n^2)\), but the size of a number says nothing about how many factors of 3 it has. The correct step uses \(n^2 \mid 2^n + 1\), which gives \(2x \le x + 1\) and so \(x \le 1\). The lifting-the-exponent lemma was also stated with variables that did not match its formula.

What changed. The proof is reorganised into steps, with the answer stated at the start. Previously titled “An Application of the LTE lemma and Fermat’s Little Theorem”.