Modular restrictions on factors of Mersenne numbers

siegert81 · 2014-03-09, 00:06

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?

Batalov · 2014-03-09, 00:33

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.

siegert81 · 2014-03-09, 00:45

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.

Batalov · 2014-03-09, 01:07

Order of an element. C.C. should have hyperlinked it from that other page.

R.D. Silverman · 2014-03-09, 01:20

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.

TheMawn · 2014-03-09, 04:34

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.

siegert81 · 2014-03-09, 12:51

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!

R.D. Silverman · 2014-03-09, 13:58

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.

siegert81 · 2014-03-09, 16:03

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.

R.D. Silverman · 2014-03-10, 12:51

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.

c10ck3r · 2014-03-11, 04:16

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.

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 2kp+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 10011101000101₂ 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, 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 = 79. 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, 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-09, 01:07	#4
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3²×1,117 Posts	Order of an element. C.C. should have hyperlinked it from that other page.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
P-1 factoring attempts at smallest-remaining Mersenne numbers with no known factors	UberNumberGeek	Factoring	51	2017-02-13 20:30
Mersenne prime factors of very large numbers	devarajkandadai	Miscellaneous Math	15	2012-05-29 13:18
Mersenne Prime Factors of v.large numbers	devarajkandadai	Miscellaneous Math	6	2006-01-04 22:44
Factors of Mersenne Numbers	asdf	Math	17	2004-07-24 14:00
Factors of Mersenne numbers ?	Fusion_power	Math	13	2003-10-28 20:52