help with a proof

vtai · 2007-06-28, 00:20

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.

paulunderwood · 2007-06-28, 11:11

http://primes.utm.edu/glossary/page....sLittleTheorem

R.D. Silverman · 2007-06-28, 11:19

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.

alpertron · 2007-06-28, 12:22

Let p be a prime number.

$2^p \equiv 1 \,\pmod {2^p-1}$

Using Fermat's Little Theorem we get:

$2^p \equiv 2 \,\pmod p$ so $2^p-1 \equiv 1 \,\pmod p$

This means that $2^p-1 = kp+1$ so we finally get:

$2^{2^p-1} \equiv 2^{kp+1} \equiv 2^{kp}*2^1 \equiv (2^p)^k*2 \equiv 1^k*2 \equiv 2\,\pmod {2^p-1}$

R. Gerbicz · 2007-06-28, 12:23

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.

paulunderwood · 2007-06-28, 12:37

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

)

alpertron · 2007-06-28, 13:35

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

paulunderwood · 2007-06-28, 13:50

vtai · 2007-06-28, 14:04

Thank your for your replies...

vtai · 2007-06-28, 14:36

i have another question that is related...what if p was not prime, how would we prove the congruence then??

alpertron · 2007-06-28, 14:50

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 $2^p\not\equiv 2\,\pmod p$ , so you will not get the number 2.

But since $2^p \eq 1\,\pmod{2^p-1}$ at least you always get a power of 2.

For example if p=6 you get:
$2^{2^p-1} \eq 2^{2^p-1 \bmod p} \eq 2^{63 \bmod 6} \eq 2^3 \eq 8\,\pmod{2^p-1}$

2007-06-28, 00:20	#1
vtai Jun 2007 3₁₆ 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, 12:22	#4
alpertron Aug 2002 Buenos Aires, Argentina 1342₁₀ Posts	Let p be a prime number. $2^p \equiv 1 \,\pmod {2^p-1}$ Using Fermat's Little Theorem we get: $2^p \equiv 2 \,\pmod p$ so $2^p-1 \equiv 1 \,\pmod p$ This means that $2^p-1 = kp+1$ so we finally get: $2^{2^p-1} \equiv 2^{kp+1} \equiv 2^{kp}2^1 \equiv (2^p)^k2 \equiv 1^k2 \equiv 2\,\pmod {2^p-1}$ Last fiddled with by alpertron on 2007-06-28 at 12:28*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
APR-CL as primality proof	f1pokerspeed	FactorDB	14	2014-01-09 21:06
...another proof down the drain?	Batalov	Math	1	2008-08-12 19:02
Proof (?!) that RH is false?	bdodson	Lounge	6	2007-03-19 17:19
A proof with a hole in it?	mfgoode	Puzzles	9	2006-09-27 16:37
A Second Proof of FLT?	jinydu	Math	5	2005-05-21 16:52

2007-06-28, 11:11	#2
paulunderwood Sep 2002 Database er0rr 2³×449 Posts	http://primes.utm.edu/glossary/page....sLittleTheorem

2007-06-28, 12:23	#5
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 5A2₁₆ 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=kp+1 for some positive integer k, using this: 2^Mp=2^(kp+1)=22^(kp)=2(2^p)^k=2(Mp+1)^k==2*1^k==2 mod Mp, what is needed.

2007-06-28, 13:50	#8
paulunderwood Sep 2002 Database er0rr E08₁₆ 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??