# Find all $n>1$ such that $\dfrac{2^n+1}{n^2}$ is an integer.

Find all $n>1$ such that $\dfrac{2^n+1}{n^2}$ is an integer.

I know that $n$ must be odd, then I don't know how to carry on. Please help. Thank you.

-
Can you find any such $n$? – Chris Eagle Sep 28 '12 at 13:25
@Chris, I can --- $n=3$. – Gerry Myerson Sep 28 '12 at 13:30
According to a brute-force computation using Python 3, there are no other such values up to 300000, so I'd concentrate on proving that no other values except 3 can exist. – MvG Sep 28 '12 at 13:49
Thanks MvG!${}$ – ᴊ ᴀ s ᴏ ɴ Sep 28 '12 at 13:54
For odd primes other than 3, it follows from Fermat's little theorem: neither $n$ does not divide $2^n+1$. Somehow $\varphi(n)$ could be considered in the general case.. – Berci Sep 28 '12 at 13:58

Let's consider $$\frac{2^n+1}{n^k}$$

If $p$ be the smallest prime that divide $n$

Let $ord_p2=d,d\mid(p-1,2n)\implies d\mid 2$ as $p-1<$ all other primes,

$\implies p\mid (2^2-1)\implies p=3.$

Let $3^r||n, 2^{2n}\equiv 1{\pmod {3^{kr}}}\implies \phi(3^{kr})|2n$ as $2$ is a primitive root of $3^s$ for all $s\ge 1$ (as mentioned in Example 8.1 in the Naoki Sato's solution mentioned in Pantelis Damianou's answer).

$\implies 2\cdot 3^{kr-1}|2n \implies kr-1\le r$ as $(3^{kr-1},\frac{n}{3^{kr}})=1$

So, $r(k-1)\le 1$

(1)If $k>2$, there will be no solution.

(2)If $k=2$

$\implies r=1,$ let $q>p=3$ be next smallest prime that divides $n$.

$ord_q2$ must divide $(q-1,2\cdot 3\cdot \frac{n}{3})$

$\implies ord_q2\mid 6$ as $q-1<$ all primes greater than $3\implies (q-1,\frac{n}{3})=1$

So, $q\mid (2^6-1)\implies q=7$, but $2^7+1=129$ is not divisible by $7$.

So, there is no prime$>3$ that satisfies the given condition $\implies n=3$ if $k=2$.

(3)If $k=1$, there is no restriction on $r>0$

Here $ord_q2$ must divide $(q-1,2\cdot 3^r\cdot \frac{n}{3^r})=(q-1,2\cdot 3^r)$

So, $q-1=2^c3^d$ as $q<$ any other primes,$\implies (q-1,2\cdot 3^r)=2\cdot 3^{min(c,r)}$

Programmatically I have observed that $n=3^s$ keep $\frac{2^n+1}{n}$ an integer, where $s$ is natural number which can be verified as follows:

As $2$ is a primitive root of $3^s$ for all $s\ge 1,$

So, If $n=3^s$ $ord_{(3^s)}2=\phi(3^s)=2\cdot 3^{s-1}\implies 2^{\frac{\phi(n)}2}\equiv -1\pmod n$

Now, $\frac{\phi(n)}2=3^{s-1}\implies 2^{3^{s-1}}\equiv -1\pmod {3^s}$

$\implies (2^{3^{s-1}})^3\equiv -1\implies 2^{3^s}\equiv -1\pmod {3^s}$

-

(IMO problem 1990)

http://www.artofproblemsolving.com/Resources/Papers/SatoNT.pdf

The solution is on page 33 in case you give up!

-

The answer is correct. I gave the idea and the start point for solving this problem. By the way, it is the first answer to be posted and @PAD found the link which gives the rest of solution. He got $10$ upvotes and this answer got some upvotes and each time some users come around and downvote it!!!. It is an attack on my answers.

Hint:since it is a number theory problem, then it may be better to consider the corresponding congruence,

$$2^n+1=k \,n^2 \Rightarrow 2^n \equiv -1 (\mathrm{mod}\, n^2) \,.$$

-
Any more further hint? – ᴊ ᴀ s ᴏ ɴ Sep 28 '12 at 14:32
@jasoncube:I already gave you the main idea to solve the problem as you can see. – Mhenni Benghorbal Sep 29 '12 at 11:01
@Downvoter:What's the downvote for? – Mhenni Benghorbal Nov 3 '12 at 22:43
@serial-downvoters: What's going on? – Mhenni Benghorbal Jan 24 '14 at 20:30
Maybe peolple are wondering "How does this help?" – Pedro Tamaroff Jan 25 '14 at 19:43