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$
proving that there is no solution for $n$ in positive integers except $n = 1$ for $2^n = nk + 1$
-
0Clearly, 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 $ – 2012-07-05
2 Answers
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) 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.