20070628, 00:20  #1 
Jun 2007
3_{16} Posts 
help with a proof
let p be a prime. show that 2^Mp = 2(mod Mp). (where Mp is the Mersenne number for p). i was able to show that the congruence is true for fermat numbers (ie. 2^Fn = 2(mod Fn)). but i just can't seem to figure it out for this question. any help with this proof would be appreciated.

20070628, 11:11  #2 
Sep 2002
Database er0rr
5^{3}·31 Posts 

20070628, 11:19  #3  
Nov 2003
16444_{8} Posts 
Quote:
M_p, not mod p. 

20070628, 12:22  #4 
Aug 2002
Buenos Aires, Argentina
2·691 Posts 
Let p be a prime number.
Using Fermat's Little Theorem we get: so This means that so we finally get: Last fiddled with by alpertron on 20070628 at 12:28 
20070628, 12:23  #5 
"Robert Gerbicz"
Oct 2005
Hungary
5×13×23 Posts 
Mp=2^p1, where p is prime. By Fermat's Little Theorem 2^p==2 mod p, so
Mp==1 mod p, so Mp=k*p+1 for some positive integer k, using this: 2^Mp=2^(k*p+1)=2*2^(k*p)=2*(2^p)^k=2*(Mp+1)^k==2*1^k==2 mod Mp, what is needed. 
20070628, 12:37  #6  
Sep 2002
Database er0rr
5^{3}·31 Posts 
Quote:
Quote:
2^p==2 (mod p) by Fermat's Little Theorem since gcd(2,2^p1)==1 2^p2==0 (mod p) by subtracting "2" from each side of the congruence equation By the definition, p divides 2^p2. That is 2^p2 is a multiple of p. So 2^p2 =N*p for some "N". 2^p1=N*p+1 by adding "1" to each side of the equation. 2^p1==0 (mod Mp) by definition 2^p==1 (mod Mp) by adding "1" to each side of the congruence equation[*] Therefore, 2^Mp==2^(N*p+1) (mod Mp) 2^Mp==(2^(N*p))*2 (mod Mp) 2^Mp==((2^p)^N)*2 (mod Mp) 2^Mp==(1^N)*2 (mod Mp) by[*] 2^Mp==2 (mod Mp) Q.E.D. This demonstrates why a base 2 Fermat test is useless for Mersenne primes. (I see that by the time I have written this out two other people have given the proof ) Last fiddled with by paulunderwood on 20070628 at 13:12 

20070628, 13:35  #7 
Aug 2002
Buenos Aires, Argentina
2×691 Posts 

20070628, 13:50  #8 
Sep 2002
Database er0rr
5^{3}·31 Posts 

20070628, 14:04  #9 
Jun 2007
3 Posts 
Thank your for your replies...

20070628, 14:36  #10 
Jun 2007
3 Posts 
i have another question that is related...what if p was not prime, how would we prove the congruence then??

20070628, 14:50  #11  
Aug 2002
Buenos Aires, Argentina
2×691 Posts 
Quote:
But since at least you always get a power of 2. For example if p=6 you get: Last fiddled with by alpertron on 20070628 at 15:02 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
APRCL as primality proof  f1pokerspeed  FactorDB  14  20140109 21:06 
...another proof down the drain?  Batalov  Math  1  20080812 19:02 
Proof (?!) that RH is false?  bdodson  Lounge  6  20070319 17:19 
A proof with a hole in it?  mfgoode  Puzzles  9  20060927 16:37 
A Second Proof of FLT?  jinydu  Math  5  20050521 16:52 