Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer

(IMO problem 1990)

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

share|cite|improve this answer

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) \,.$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.