Determine all integers $n>1$ such that $\frac{2^{n}+1}{n^{2}}$ is an integer.
This exercise is a classic: it is problem 3 of the 1990 International Olympiad, held in Beijing, where France placed 5th with three gold medals, notably thanks to Vincent Lafforgue (younger brother of Fields Medalist Laurent Lafforgue), who achieved perfect scores of 42/42 in 1990 and 1991. It is worth noting, however, that there were half as many participating countries then as there are today: several European countries subsequently split up.

This exercise uses reasoning techniques that have become classic and useful for a wide range of problems. First, the idea is to look for the smallest prime factor \( p \) of \( n \), using the concept of the order of 2 modulo \( p \). Since \( n \) is odd, \( p \geq 3 \). The order of 2 modulo \( p \) is the smallest non-zero exponent \( b \) such that \( 2^b \equiv 1 \pmod{p} \), and it is shown that \( b \) divides any other exponent \( a \) such that \( 2^a \equiv 1 \pmod{p} \). It suffices to write the Euclidean division \( a = bq + r \) and note that \( 2^{bq} \equiv 1 \pmod{p} \) to deduce \( 2^r \equiv 1 \pmod{p} \), with \( 0 \leq r < b \). Since \( b \) is the smallest positive integer satisfying this relation, necessarily \( r = 0 \) so \( a = bq \).

According to Fermat's theorem, \( 2^{p-1} \equiv 1 \pmod{p} \), which implies that the order of 2 divides \( p-1 \). And since \( p \) divides \( n \), and thus \( 2^n + 1 \), and \( 2^{2n} - 1 = (2^n + 1)(2^n - 1) \), the order of 2 also divides \( 2n \). It is coprime with \( n \), since it is strictly less than \( p \) and \( p \) is, by hypothesis, the smallest divisor of \( n \) other than 1 (the order of 2 cannot obviously be 1, as for no prime \( p \neq 2 \) is 1 congruent to 1 modulo \( p \)). Therefore, by Gauss's theorem, it divides 2: it can only be 2, so \( p \) divides \( 2^2 - 1 = 3 \), and the smallest prime factor \( p \) of \( n \) is necessarily 3.

If we were to look for integers \( n \) such that \( n \) divides \( 2^n + 1 \), there would be many, and their prime factors could be numerous, even if the smallest of them is necessarily 3. For example, if \( n \) divides \( 2^n + 1 = nq \), \( 2^n + 1 \) divides \( 2^{nq} + 1 = 2^{2^n + 1} \) because \( q \) is odd, so \( 2^n + 1 \) is also a solution. 3, 9, but also \( 513 = 2^9 + 1 \) and even one-third of 513, \( 171 = 9 \times 19 \), are solutions. Only these numbers do not satisfy \( 2^n + 1 \) being divisible by \( n^2 \), because, for example, \( 2^9 + 1 = 3^3 \times 19 \) is not divisible by \( 9^2 = 3^4 \).

The second step of the proof is to show that \( n \) cannot be divisible by 9. Let \( n = 3^k d \), with \( k \geq 1 \) and \( d \) odd and not divisible by 3. We will prove by induction on \( k \) that the highest power of 3 dividing \( 2^n + 1 \) is \( 3^{k+1} \). For \( k = 1 \), \( 2^{3d} + 1 = (2^3 + 1)(2^{3(d-1)} - 2^{3(d-2)} + \cdots - 2^3 + 1) \). The second parenthesis contains a sum of \( d \) terms all congruent to 1 modulo 9, since \( 2^3 \equiv -1 \pmod{9} \), so it is congruent to \( d \) modulo 9, which implies that it is not a multiple of 3, and the first parenthesis is precisely 9, which initializes the induction by proving the result for \( k = 1 \), regardless of the factor \( d \). Now if the result is true for a given \( k \geq 1 \), since \( 2^{3n} + 1 = (2^n + 1)(2^{2n} - 2^n + 1) \) and \( 2^n \equiv -1 \pmod{3^{k+1}} \), \( 2^{2n} - 2^n + 1 \equiv 1 + 1 + 1 = 3 \pmod{9} \) is divisible by 3 but not by 9, which completes the proof. It follows that if \( k \geq 2 \) and \( n = 3^k d \), the highest power of 3 dividing \( 2^n + 1 \) is \( 3^{k+1} \), while \( n^2 \) is divisible by \( 3^{2k} \). Therefore, a solution to our problem must be a multiple of 3 and not a multiple of 9.

This result generalizes by an analogous proof: for a given prime \( p \), if we denote \( v_p(n) \) the exponent of the highest power of \( p \) dividing \( n \), and if \( a \) and \( b \) are integers such that \( p \) divides \( a - b \) but does not divide \( a \) or \( b \), then:

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

This is the LTE (Lifting The Exponent) theorem, which allows solving many exercises. In the present problem, we apply this LTE theorem for \( p = 3 \), \( a = 2 \), and \( b = -1 \).

What can we say now about the factor \( d \)? For which values of \( d \) not multiples of 3 is \( 2^n + 1 \) divisible by \( n^2 \) with \( n = 3d \)? Let \( p \) be the smallest prime factor of \( d \) (\( p \geq 5 \)). The order of 2 modulo \( p \) divides \( p-1 \) by Fermat's theorem, but it also divides \( 2n = 6d \) since \( 2^{2n} \equiv 1 \pmod{p} \), and it does not divide \( n \) since \( 2^n \equiv -1 \pmod{p} \), so it is even. Since it is strictly less than \( p \), the smallest prime factor of \( d \), it is coprime with \( d \). Therefore, it divides 6 (by Gauss's theorem). The only even divisors of 6 are 2 and 6, but 2 cannot be the order of 2 because \( 2^2 - 1 = 3 \) has no prime factor other than 3, and it cannot be the order of 6 because \( 2^6 - 1 = 3^2 \times 7 \) has \( p = 7 \) as its only prime factor different from 3, but 7 is not of order 6 but of order 3 (it divides \( 2^3 - 1 \), so it also divides \( 2^{3d} - 1 \) and not \( 2^{3d} + 1 \)). Since \( d \) cannot have a smallest prime factor, \( d = 1 \), so the only integer \( n \) such that \( \frac{2^n + 1}{n^2} \) is an integer, besides the trivial solution \( n = 1 \), is \( n = 3 \).