Integer Problem With An Integer Answer

It is easy to guess that $n=3$ is a unique solution. Let us prove it.

We divide the proof into several steps. The first step is to consider the minimal prime divisor $p$ of $n$ , and from $n \mid (2^n +1)$ we can deduce $p=3$ .

---

Proof:

Clearly $n$ is odd. Let $r_1$ be the order of $2$ modulo $p$ . By $2^n \equiv -1 \pmod{n}$ we have

$2^{2n}\equiv 1\pmod{p}\cdots(1)$

As $p \geq 3$ , by Fermat's Little Theorem, we get

$2^{p-1}\equiv 1\pmod{p}\cdots(2)$

$(1)$ and $(2)$ and the properties of order imply $r_1 \mid 2n$ and $r_1 \mid (p-1)$ , so $r_1 \mid \gcd(2n,p-1)$ . It is easy to prove $\gcd(2n,p-1)=2$ . This is because from $2 \not\mid n$ one has $2\mid \gcd(2n,p-1)$ , and $2^2\not\mid \gcd(2n,p-1)$ . On the other hand, if there is an odd prime $q$ such that $q\mid \gcd(2n,p-1)$ , then $q\mid (p-1)$ and $q\mid n$ , but the former shows $q<p$ . This contradicts the fact that $p$ is the minimal prime divisor of $n$ . So $\gcd(2n,p-1)=2$ , thus $r_1=2$ , and $p=3$ .

---

Hence we can assume

$n=3^mc, m\geq 1, 3\not\mid c\cdots(3)$

In the second step, we prove $m=1$ . By $n^2 \mid (2^n+1)$ we have $2^{3^mc}\equiv -1\pmod{3^{2m}}$ , thus

$2^{2\times3^mc}\equiv 1\pmod{3^{2m}}\cdots(4)$

If $m\geq 2$ , then we get that the order of $2$ modulo $3^{2m}$ is $2\times 3^{2m-1}$ (The proof is left as an exercise to the reader). So $(4)$ implies $2\times 3^{2m-1}\mid 2\times 3^mc$ , i.e. $3^{m-1}\mid c$ . Thus $3\mid c$ (as $m\geq 2$ ), which contradicts $3\not\mid c$ in $(3)$ . So $m=1$ .

In the third step, we prove $c=1$ in $(3)$ . This can be done similarly as the first step.

If $c>1$ , let $s$ be the least prime divisor of $c$ , then

$2^{3c}\equiv -1 \pmod{s}\cdots(5)$

Let $r_2$ be the order of $2$ modulo $s$ . By $(5)$ we have $2^{6c}\equiv 1\pmod{s}$ . Furthermore we also have $2^{s-1}\equiv 1\pmod{s}$ , so $r_2 \mid 6c$ and $r_2 \mid (s-1)$ , thus $r_2 \mid \gcd(6c,s-1)$ . According to the choice of $s$ we have $\gcd(s-1,c)=1$ , so $r_2\mid 6$ . Also, $2^{r_2}\equiv 1\pmod{s}$ implies $s=3$ or $7$ . It is easy to see that $s=3$ is impossible, and by $(5)$ , $s=7$ is impossible too. Thus $c=1$ , and $n=3$ .

Note that if we first prove $c=1$ in $(3)$ , then it would not work well. Here the order of proof is very important. Besides, the identity $m=1$ in the second step can also be proved by comparing the powers of primes as follows.

It follows from the binomial theorem that

$2^n+1=(3-1)^n+1=3n+\sum_{k=2}^{n}(-1)^k \binom{n}{k}3^k\cdots(6)$

Let $3^a \mid k!$ . Then

$\alpha=\sum_{l=1}^{\infty}\left[\frac{k}{3^l}\right]<\sum_{l=1}^{\infty}\frac{k}{3^l}=\frac{k}{2}.$

Thus by

$\binom{n}{k}3^k = \frac{n(n-1)\cdots(n-k+1)}{k!}3^k$

we have that $\binom{n}{k}3^k$ is divisible by $3^{\beta}$ , and $\beta$ satisfies (note that $k\geq 2$ )

$\beta\geq k+m-\alpha>k+m-\frac{k}{2}\geq m+1,$

so $\beta \geq m+2.$ Thus the sum on the right side of $(6)$ is divisible by $3^{m+2}$ . If $m>1$ , then $2m\geq m+2,$ so it follows from $3^{2m}\mid (2^n+1)$ and $(6)$ that $3^{m+2}\mid 3^n$ , i.e. $3^{m+1}\mid n$ , in contradiction with $(3)$ . Thus $m=1$ .

Hence the conclusion is proven, and we are done.