# 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
• 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
• You may answer this question with all kind of methods. – A. Chu Sep 28 '12 at 14:51

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

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

Let $$\operatorname{ord}_p2=d,d\mid(p-1,2n)\implies d\mid 2$$ as $$p-1<$$ all other primes, so it 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).

This 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$$ then $$r=1;$$ let $$q>p=3$$ be next smallest prime that divides $$n$$. Now $$\operatorname{ord}_q2$$ must divide $$(q-1,2\cdot 3\cdot \frac{n}{3})$$

Then $$\operatorname{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, which implies $$(q-1,2\cdot 3^r)=2\cdot 3^{\min(c,r)}$$

Programmatically I have observed that $$n=3^s$$ keeps $$\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$$, $$\operatorname{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}$$.

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