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.

Here is a problem which i have not been able to do for quite sometime.

  • For $n \geq 2$, show that $n \nmid 2^{n}-1$.

I have thought of proving this in two ways: One by using induction which didn't actually work. Next by Fermat's little theorem we have $2^{p-1} \equiv 1 \ (\text{mod} \ p)$, which actually says that for $p \mid 2^{p}-2$. But i couldn't proceed more than this. Any ideas by which i can actually solve the problem?

share|improve this question

2 Answers 2

up vote 12 down vote accepted

HINT $\ \ $ Prime $\rm\ P|N\ \Rightarrow\ 2^{P-1}\equiv 1\equiv 2^N\ \Rightarrow\ 2^{GCD(P-1,N)} \equiv 1\ \ (mod\ P)\ $

But if $\rm\:P\:$ is the least prime factor of $\rm\:N\:$ then $\rm\ GCD(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
    
Thanks bill –  anonymous Feb 5 '11 at 3:51
    
I have attempted something. Please see if it's correct, and if there is a mistake i request you to help me out. –  anonymous Feb 13 '11 at 16:00
    
Thanks for pointing out the mistake –  anonymous Feb 13 '11 at 17:11
    
How did you find that mistake bill. Great, i couldn't find anything while i was trying to prove it. Feels bad, since my efforts have gone waste :x) –  anonymous Feb 16 '11 at 16:24
1  
@Saurabh Suppose, for contradiction, $\rm\:N\:|\:2^N\!-\!1,\:$ and prime $\rm\:P\:|\:N.\:$ Since $\rm\:2^N\!-\!1\:$ is odd, so is $\rm\:P.\:$ Now $\rm\:P\:|\:N\:|\:2^N\!-\!1\:\Rightarrow\:2^N\equiv 1\pmod P.\:$ Also $\rm\:2^{P-1}\equiv 1\pmod P\:$ by little Fermat. By Bezout, $\rm\:gcd(N,P\!-\!1)\, =\, J\:N+K\:(P\!-\!1)\:$ for $\rm\:J,K\in \mathbb Z.\:$ Hence $$\rm 2^{gcd(N,P-1)} \equiv 2^{\:J\:N+K\:(P-1)} \equiv (2^N)^{\!\:J} (2^{P-1})^K \equiv 1^J\, 1^K \equiv 1\pmod P$$ –  Bill Dubuque Jun 11 '12 at 17:07

You can look at this modulo the smallest prime factor $p$ of $n$.

Write $n=p^rm$ where $m$ is a product of primes greater than $p$. Then $m$ will be coprime to $p-1$, so $ma=1$ (mod $p-1$) for some positive integer $a$. Now use Fermat's little theorem $$ (2^n)^a=2^{p^rma}=2^{p^r}=2\not=1\qquad{\rm(mod\ }p{)}. $$

[Edit: Even better - $n$ will be coprime to $p-1$, as Bill notes in his answer, so there is no need to extract out the $p^r$ factor.]

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.