20140309, 00:06  #1 
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^(q1)1, due to Fermat's little theorem, and I understand that (apparently) p divides q1, which easily leads to the conclusion. I don't understand how FLT leads to p dividing q1. Is anybody out there knowledgeable and kind enough to help me understand this piece of the Mersenne puzzle? 
20140309, 00:33  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10011101000101_{2} Posts 
There's this page at UTM. Maybe someone will explain that in easier terms?
___________________________________________ Interestingly (similarly),
Last fiddled with by Batalov on 20140309 at 00:43 Reason: GQ and EQ's 
20140309, 00:45  #3  
Dec 2010
4A_{16} Posts 
Quote:


20140309, 01:20  #5  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
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. 

20140309, 04:34  #6 
May 2013
East. Always East.
11·157 Posts 
2kp+1 or +/ 1 (mod 8). The second one is important. 2^61 = 63 = 7*9.
Now whether or not this proof is good for composite exponents is unknown to me. Last fiddled with by TheMawn on 20140309 at 04:34 
20140309, 12:51  #7 
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, q1 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 q1, 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 20140309 at 12:59 
20140309, 13:58  #8  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,877 Posts 
Quote:
Quote:
Exercize for the student: determine what he said that was wrong. 

20140309, 16:03  #9 
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^(p1) is congruent to 1 (mod p). As a result, p1 is divisible by q, and p=2kq+1. Last fiddled with by siegert81 on 20140309 at 16:08 
20140310, 12:51  #10 
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,877 Posts 

20140311, 04:16  #11 
Aug 2010
Kansas
547 Posts 
Quoted for posterity's sake. Your proofreading comment becomes rather ironic given your grammatical error in the above quote.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
P1 factoring attempts at smallestremaining Mersenne numbers with no known factors  UberNumberGeek  Factoring  51  20170213 20:30 
Mersenne prime factors of very large numbers  devarajkandadai  Miscellaneous Math  15  20120529 13:18 
Mersenne Prime Factors of v.large numbers  devarajkandadai  Miscellaneous Math  6  20060104 22:44 
Factors of Mersenne Numbers  asdf  Math  17  20040724 14:00 
Factors of Mersenne numbers ?  Fusion_power  Math  13  20031028 20:52 