# proving that there is no solution for $n$ in positive integers except $n = 1$ for $2^n = nk + 1$

If $k$ is a positive integer, how to prove that there is no solution for $n$ in positive integers except $n = 1$ for $2^n = nk + 1$

-
Clearly, n is odd, else the R.H.S. will be odd. If n is prime=p(say), $2^p-1=(1+1)^p-1≡1(mod\ p)\ as\ p|nCp$ – lab bhattacharjee Jul 5 '12 at 10:38

The reason is that the only solution to the congruence $2^n\equiv 1\mod n$ is $n=1$.

Assume there exist solution $n>1$ of the congruence written above and consider smallest prime $p\;|\;n$. Then $2^n\equiv 1\mod p$, and $\mathrm{ord}_p(2)\;|\;n$. Recall that $\mathrm{ord}_p(2)<p$ and $p$ is the smallest prime divisor of $n$, then $\mathrm{ord}_p(2)=1$. This means then $p\;|\; 2^1-1=1$, which is impossible for prime number $p$. Contradiction.

-

Hint $\ \$ Prime $\rm\ P\,|\,N\ \Rightarrow\ 2^{P-1}\equiv 1\equiv 2^N\ \Rightarrow\ 2^{\,\color{#C00}{(P-1,N)}} \equiv 1\ \ (mod\ P)\$

But if $\rm\:P\:$ is the least prime factor of $\rm\:N\:$ then $\rm\,\color{#C00}{(P\!-\!1,N)} = 1\:.$

I.e. $\rm\ mod\ P\$ the order of $\rm\:2\:$ is $\:1\:$ since it divides the coprime integers $\rm\:P\!-\!1\:$ and $\rm\:N\:.$

Note $\$ This problem was posted to sci.math on 2009\11\03. $\$ There I remarked that the proof shows that if $\rm\ A^N = 1\$ then the order of $\rm\:A\:$ is $\ge$ the least prime factor $\rm\:P\:$ of $\rm\:N.\:$ In particular this implies that $\rm\ A^{P-1}\!\ne 1\:,\$ which settles the problem at hand.

-