How many rationals of the form $\large \frac{2^n+1}{n^2}$ are integers?

This was Problem 3 (first day) of the 1990 IMO. A full solution can be found here.

It's a bit late to post this answer. But I found this question can be solved using the Lifting the exponent lemma with so much ease.

Theorem: Let $x$ and $y$ be two integers and $n$ is an odd integer. Let $p$ be an od prime such that $p|x+y$ and none of $x$ and $y$ are divisible by $p$. Then we have,

$v_p(x^n+y^n)=v_p(x+y)+v_p(n)$

$v_p(N)$ denotes the highest power of $p$ which divides $N$.

Solution:

Claim: If $n$ divides $2^n+1$ then $n$ is a perfect power of $3$.

Proof:

Let $p$ be a smallest prime factor of $n$,

That means $2^n \equiv -1 \pmod p \implies 2^{2n} \equiv 1 \pmod p$. And also $2^{p-1} \equiv 1 \pmod p \implies 2^{\gcd(2n,p-1)} \equiv 1 \pmod p$

Now, since $p$ is the smallest divisor of $n$ the $\gcd(2n,p-1)=2 \implies 2^2 \equiv 1 \pmod p \implies p=3$, therefore, $n=3^m \cdot k \text { and } 3 \nmid k$, if $k$ is greater than $1$, the similar argument would show $3 |k$. Contradiction.

So we have $3^{\alpha} || n \implies 3^{\alpha+1} \nmid n $

$v_3(2^n+1) \ge v_3(n^2)$

$v_3(2+1)+v_(n) \ge v_3(n^2)$

$1+ \alpha \ge 2\alpha \implies \alpha =1,0$

$\implies v_3(n)=1,0$

$n=1 \text{ or } 3$

Andre's modification of a wrong answer :)

If $n=3^k$, then

$$2^n+1=2^{3^k}+1=2^{3 \cdot 3^{k-1}}+1= (2^{3^{k-1}}+1)( 2^{2 \cdot 3^{k-1}}-2^{ \cdot 3^{k-1}}+1) $$

The second bracket is never divisible by $9$, thus by induction one can prove that $3^{2k-1}$ doesn't divide $2^n+1$.

Note: Since Geoff's answer was wrong, and this post doesn't make too much sense anymore, a simple observation:

If $n \neq 1$, then $3|n$.

Indeed let $p$ be the smallest prime divisor of $n$.

Then $2^{p-1} \equiv 1 \mod p$ and $2^{2n} \equiv (-1)^2 \equiv 1 \mod p$.

Thus $2^d \equiv 1 \mod p$ where $d=gcd(p-1,2n)$. But no prime factor of $p-1$ can divide $n$, since $p$ is the smallest one, thus $gcd(p-1,n)=1$. Hence $d |2$.

$2^d \equiv 1 \mod p$ implies now that $p=3$.

This proves that $n=3^km$ for some $k \geq 1$ and $m $ relatively prime to $3$. I wonder if the first argument can be modified for this case:

$$2^n+1=2^{3^km}+1=2^{3 \cdot 3^{k-1}m}+1= (2^{3^{k-1}m}+1)( 2^{2 \cdot 3^{k-1}m}-2^{ \cdot 3^{k-1}m}+1) $$

Since $9$ doesn't divide the second bracket we get that $3^{2k-1}$ must divide $(2^{3^{k-1}m}+1)$ and repeating I think we get $3^{k}$ divides $2^m+1$...

It is easy to prove that $2^m \equiv -1 \mod 9$ implies $3 |m$ (this follows from $2^3 \equiv -1 mod 9$ and $ord(2)=6$).

Hence $k=1$, and we must have $n=3 m$ with $gcd(3,m)=1$...

Now, lets try the same again.

Suppose by contradiction $m \neq 1$. Let $q$ be the smallest prime factor of $m$.

Then

$2^d \equiv 1 \mod q$ where $d=gcd(q-1,2n)$. But no prime factor of $p-1$ can divide $n$, excepting $3$, Hence $d |6$.

This implies that

$$2^6 \cong 1 \mod q \,.$$

Thus, the only possible values of $q$ is $q=7$.

But this is not possible since $2^{3m}+1 \equiv 1+1 \mod 7$, thus $7$ cannot divide $2^n+1$.