mersenneforum.org  

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

Reply
 
Thread Tools
Old 2014-03-09, 00:06   #1
siegert81
 
Dec 2010

2×37 Posts
Default 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?
siegert81 is offline   Reply With Quote
Old 2014-03-09, 00:33   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

217368 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2014-03-09, 00:45   #3
siegert81
 
Dec 2010

2·37 Posts
Default

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.
siegert81 is offline   Reply With Quote
Old 2014-03-09, 01:07   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts
Default

Order of an element. C.C. should have hyperlinked it from that other page.
Batalov is offline   Reply With Quote
Old 2014-03-09, 01:20   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by siegert81 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2014-03-09, 04:34   #6
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

11·157 Posts
Default

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
TheMawn is offline   Reply With Quote
Old 2014-03-09, 12:51   #7
siegert81
 
Dec 2010

2×37 Posts
Default

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
siegert81 is offline   Reply With Quote
Old 2014-03-09, 13:58   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by siegert81 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2014-03-09, 16:03   #9
siegert81
 
Dec 2010

10010102 Posts
Default

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
siegert81 is offline   Reply With Quote
Old 2014-03-10, 12:51   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by siegert81 View Post
Actually, I *DO* get it, but I used the letter p instead of q, on accident.
....proofreading is usually useful.
R.D. Silverman is offline   Reply With Quote
Old 2014-03-11, 04:16   #11
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

547 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
c10ck3r is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 18:02.

Thu Dec 3 18:02:03 UTC 2020 up 14:13, 1 user, load averages: 2.25, 2.12, 2.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.