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

Question

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

How many rationals of the form $\large \frac{2^n+1}{n^2},$ $(n \in \mathbb{N} )$ are integers?

The possible values of $n$ that i am able to find is $n=1$ and $n=3$, so there are two solutions and this seems to be the answer to this problem.

But now we have to prove that no more of such $n$ exists, and thus the proof reduces to: Proving that $n^2$ does not divides $2^n+1$ for any $n \gt 3$.

Does anybody know how to prove this?

Answer 1

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

Answer 2

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$.

Answer 3

I've translated the handling of the problem into a certain notation, which I find very useful for formal algebraic manipulation of exponential diophantine problems, and provide a solution in that formalism. The Woeginger-solution was already linked by André Nicolas so my proposed way of solving this is now only for that reader who might be interested into that -hopefully: much general- formalism. Here is the link so far. (I'm a bit lazy to recode the text into latex/mathjax here after the original fiddling with word/word-to-pdf. Maybe I can put it into mathjax after the weekend, if there is any interest at all)