mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-06-28, 00:20   #1
vtai
 
Jun 2007

3 Posts
Default 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.
vtai is offline   Reply With Quote
Old 2007-06-28, 11:11   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

398410 Posts
Default

http://primes.utm.edu/glossary/page....sLittleTheorem
paulunderwood is online now   Reply With Quote
Old 2007-06-28, 11:19   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
And? Note that while p is prime, M_p usually isn't. We are working mod
M_p, not mod p.
R.D. Silverman is offline   Reply With Quote
Old 2007-06-28, 12:22   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×32×79 Posts
Default

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}

Last fiddled with by alpertron on 2007-06-28 at 12:28
alpertron is offline   Reply With Quote
Old 2007-06-28, 12:23   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts
Default

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.
R. Gerbicz is offline   Reply With Quote
Old 2007-06-28, 12:37   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24×3×83 Posts
Default

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
paulunderwood is online now   Reply With Quote
Old 2007-06-28, 13:35   #7
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·32·79 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
alpertron is offline   Reply With Quote
Old 2007-06-28, 13:50   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24×3×83 Posts
Default

paulunderwood is online now   Reply With Quote
Old 2007-06-28, 14:04   #9
vtai
 
Jun 2007

3 Posts
Default

Thank your for your replies...
vtai is offline   Reply With Quote
Old 2007-06-28, 14:36   #10
vtai
 
Jun 2007

3 Posts
Default

i have another question that is related...what if p was not prime, how would we prove the congruence then??
vtai is offline   Reply With Quote
Old 2007-06-28, 14:50   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

58E16 Posts
Default

Quote:
Originally Posted by vtai View Post
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}

Last fiddled with by alpertron on 2007-06-28 at 15:02
alpertron is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 23:49.


Mon Jan 24 23:49:15 UTC 2022 up 185 days, 18:18, 0 users, load averages: 0.89, 0.97, 1.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔