 mersenneforum.org > Math help with a proof
 Register FAQ Search Today's Posts Mark Forums Read  2007-06-28, 00:20 #1 vtai   Jun 2007 316 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.   2007-06-28, 11:11 #2 paulunderwood   Sep 2002 Database er0rr 53·31 Posts    2007-06-28, 11:19   #3
R.D. Silverman

Nov 2003

164448 Posts Quote:
 Originally Posted by paulunderwood http://primes.utm.edu/glossary/page....sLittleTheorem
And? Note that while p is prime, M_p usually isn't. We are working mod
M_p, not mod p.   2007-06-28, 12:22 #4 alpertron   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 2007-06-28 at 12:28   2007-06-28, 12:23 #5 R. Gerbicz   "Robert Gerbicz" Oct 2005 Hungary 5×13×23 Posts Mp=2^p-1, 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.   2007-06-28, 12:37   #6
paulunderwood

Sep 2002
Database er0rr

53·31 Posts Quote:
 And? As this is not the homework section...

Quote:
 Note that while p is prime, M_p usually isn't. We are working mod M_p, not mod p.
Thanks for pointing this out, Bob.

2^p==2 (mod p) by Fermat's Little Theorem since gcd(2,2^p-1)==1
2^p-2==0 (mod p) by subtracting "2" from each side of the congruence equation

By the definition, p divides 2^p-2. That is 2^p-2 is a multiple of p. So 2^p-2 =N*p for some "N".
2^p-1=N*p+1 by adding "1" to each side of the equation.

2^p-1==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 2007-06-28 at 13:12   2007-06-28, 13:35   #7
alpertron

Aug 2002
Buenos Aires, Argentina

2×691 Posts Quote:
 Originally Posted by paulunderwood 2^p==2 (mod p) by Fermat's Little Theorem since gcd(2,2^p-1)==1
It should be ...since gcd(2,p)==1   2007-06-28, 13:50 #8 paulunderwood   Sep 2002 Database er0rr 53·31 Posts     2007-06-28, 14:04 #9 vtai   Jun 2007 3 Posts Thank your for your replies...   2007-06-28, 14:36 #10 vtai   Jun 2007 3 Posts i have another question that is related...what if p was not prime, how would we prove the congruence then??   2007-06-28, 14:50   #11
alpertron

Aug 2002
Buenos Aires, Argentina

2×691 Posts Quote:
 Originally Posted by vtai i have another question that is related...what if p was not prime, how would we prove the congruence then??
In that case in general , so you will not get the number 2.

But since at least you always get a power of 2.

For example if p=6 you get:

Last fiddled with by alpertron on 2007-06-28 at 15:02   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post f1pokerspeed FactorDB 14 2014-01-09 21:06 Batalov Math 1 2008-08-12 19:02 bdodson Lounge 6 2007-03-19 17:19 mfgoode Puzzles 9 2006-09-27 16:37 jinydu Math 5 2005-05-21 16:52

All times are UTC. The time now is 16:29.

Tue Oct 26 16:29:13 UTC 2021 up 95 days, 10:58, 0 users, load averages: 1.55, 1.44, 1.40