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

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?

-
 If 2|n then 2|2^n+1, therefore n is odd. – user16697 Jan 7 '12 at 20:05 @QED:Yes, I have noticed that. – Quixotic Jan 7 '12 at 20:07 It's useful to add it then. – user16697 Jan 7 '12 at 20:07 @Geoff: Click here, scroll to bottom. – cardinal Jan 7 '12 at 21:36 You tagged this contest math, what contest or preparation book are you talking about? – Will Jagy Jan 7 '12 at 21:43
show 1 more comment

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

-
All that I find there today is "The network path was not found." archive.org doesn't have it cached either. – Peter Taylor Jan 11 '12 at 12:24
I find the same here.The problem can be seen here – Quixotic Jan 11 '12 at 13:23
The cached version, seem to be accessible as of now. – Quixotic Jan 11 '12 at 13:41

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

-
Hmm. Did you try $k=2$? – cardinal Jan 7 '12 at 20:32
Let $k=2$. We have $2^9+1=(27)(19)$. This is not divisible by $3^4$. – André Nicolas Jan 7 '12 at 20:33
@N.S.: Your argument, turned around a bit, will work to show there is nothing beyond $3$. We need only verify that $x^2-x+1$ is never congruent to $0$ modulo $9$. – André Nicolas Jan 7 '12 at 20:36
@N.S.: Only a detail was wrong, the factoring idea was a good one. So modification, to show $2^{3^k}+1$ is not even divisible by $3^{k+2}$, sounds better to me than deletion. – André Nicolas Jan 7 '12 at 20:47
@N.S.: My comment said that $x^2-x+1$ is not divisible by $9$. It can be divisible by $3$, and indeed is when $x$ is an odd power of $2$. Can you change things? – André Nicolas Jan 7 '12 at 21:35