mersenneforum.org > Math Modular restrictions on factors of Mersenne numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2014-03-09, 00:06 #1 siegert81   Dec 2010 2·37 Posts Modular restrictions on factors of Mersenne numbers Could anybody please help me understand why any factor of Mp must be of the form 2*k*p+1? I understand that any factor q divides 2^(q-1)-1, due to Fermat's little theorem, and I understand that (apparently) p divides q-1, which easily leads to the conclusion. I don't understand how FLT leads to p dividing q-1. Is anybody out there knowledgeable and kind enough to help me understand this piece of the Mersenne puzzle?
 2014-03-09, 00:33 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100111010001012 Posts There's this page at UTM. Maybe someone will explain that in easier terms? ___________________________________________ Interestingly (similarly), for Gaussian-Mersenne candidates, only factors of form 4kp+1 need to be considered, and for Eisenstein-Mersenne candidates, only factors of form 6kp+1 need to be considered ...and the same for their sign complements (divided by 5 and 7, respectively); some call them GQ and EQ PRPs. Last fiddled with by Batalov on 2014-03-09 at 00:43 Reason: GQ and EQ's
2014-03-09, 00:45   #3
siegert81

Dec 2010

4A16 Posts

Quote:
 the order of 2 (mod p) divides the prime q, so it must be q
I don't know what the word "order" means here. I've seen two other proofs that don't use the word "order". My number theory book uses the greatest common divisor function, but it references a seemingly invalid lemma from an earlier chapter.

 2014-03-09, 01:07 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 32×1,117 Posts Order of an element. C.C. should have hyperlinked it from that other page.
2014-03-09, 01:20   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

Quote:
 Originally Posted by siegert81 Could anybody please help me understand why any factor of Mp must be of the form 2*k*p+1? I understand that any factor q divides 2^(q-1)-1, due to Fermat's little theorem, and I understand that (apparently) p divides q-1, which easily leads to the conclusion. I don't understand how FLT leads to p dividing q-1. Is anybody out there knowledgeable and kind enough to help me understand this piece of the Mersenne puzzle?
You are using the wrong theorem. Fermat's little theorem is inadequate
by itself. Instead, look up Lagrange's Theorem.

Definition: Within a group G, the order of an element a is the smallest integer x, such that a^x = e, where e is the group identity.

 2014-03-09, 04:34 #6 TheMawn     May 2013 East. Always East. 11·157 Posts 2kp+1 or +/- 1 (mod 8). The second one is important. 2^6-1 = 63 = 7*9. Now whether or not this proof is good for composite exponents is unknown to me. Last fiddled with by TheMawn on 2014-03-09 at 04:34
 2014-03-09, 12:51 #7 siegert81   Dec 2010 2·37 Posts Now I get it. Thank you. The order is the smallest exponent such that the congruency is one. 2^p is congruent to one, and p is prime, so p is the order. It's the smallest possible exponent. Therefore, q-1 is divisible by p, and the rest is simple algebra. Beautiful. TheMawn, if the exponent is composite, then 2^c is congruent to one, but c may not be the order as c is not prime. If d is a factor of c, 2^d could be congruent to one, and d could be the order. While d would divide q-1, c might not. So for composite exponents, I suppose one of the factors of the composite would likely replace the "p" value in "2kp+1". As for the +/- 1 (mod 8) rule, I don't understand quadratic residues yet. I'll get there though! Last fiddled with by siegert81 on 2014-03-09 at 12:59
2014-03-09, 13:58   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

Quote:
 Originally Posted by siegert81 Now I get it. Thank you. The order is the smallest exponent such that the congruency is one. 2^p is congruent to one, and p is prime, so p is the order.
No, you DON'T get it. 2^p is NOT congruent to 1. Take another look.

Quote:
 As for the +/- 1 (mod 8) rule, I don't understand quadratic residues yet. I'll get there though!
'The Mawn' got it wrong as well. Which is par for him.

Exercize for the student: determine what he said that was wrong.

 2014-03-09, 16:03 #9 siegert81   Dec 2010 2·37 Posts Actually, I *DO* get it, but I used the letter p instead of q, on accident. If p is a prime factor of Mq, then 2^q is congruent to 1 (mod p). Any power of 2 that is congruent to 1 (mod p) must be a multiple of the order of 2 (mod p). Since q is prime, q is the order of 2 (mod p). Due to FLT, 2^(p-1) is congruent to 1 (mod p). As a result, p-1 is divisible by q, and p=2kq+1. Last fiddled with by siegert81 on 2014-03-09 at 16:08
2014-03-10, 12:51   #10
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

Quote:
 Originally Posted by siegert81 Actually, I *DO* get it, but I used the letter p instead of q, on accident.
....proofreading is usually useful.

2014-03-11, 04:16   #11
c10ck3r

Aug 2010
Kansas

547 Posts

Quote:
 Originally Posted by R.D. Silverman No, you DON'T get it. 2^p is NOT congruent to 1. Take another look. 'The Mawn' got it wrong as well. Which is par for him. Exercize for the student: determine what he said that was wrong.
Quoted for posterity's sake. Your proofreading comment becomes rather ironic given your grammatical error in the above quote.

 Similar Threads Thread Thread Starter Forum Replies Last Post UberNumberGeek Factoring 51 2017-02-13 20:30 devarajkandadai Miscellaneous Math 15 2012-05-29 13:18 devarajkandadai Miscellaneous Math 6 2006-01-04 22:44 asdf Math 17 2004-07-24 14:00 Fusion_power Math 13 2003-10-28 20:52

All times are UTC. The time now is 11:46.

Wed Feb 1 11:46:23 UTC 2023 up 167 days, 9:14, 0 users, load averages: 0.88, 0.82, 0.84

Copyright ©2000 - 2023, 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.

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