23
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you find any such $n$? $\endgroup$ – Chris Eagle Sep 28 '12 at 13:25
  • 3
    $\begingroup$ @Chris, I can --- $n=3$. $\endgroup$ – Gerry Myerson Sep 28 '12 at 13:30
  • $\begingroup$ 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. $\endgroup$ – MvG Sep 28 '12 at 13:49
  • $\begingroup$ 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.. $\endgroup$ – Berci Sep 28 '12 at 13:58
  • $\begingroup$ You may answer this question with all kind of methods. $\endgroup$ – A. Chu Sep 28 '12 at 14:51
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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