Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
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

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.