20200814, 21:44  #1 
Mar 2016
353 Posts 
is the factorisation of Mp1 an advantage ?
A peaceful and pleasant night for you,
if I know the factorisation or a part of the factorisation of Mp1 do I have any advantages for checking the primality ? (Mp should be a Mersenne number) Or in other words, is the factorisation of p1 helpful ? I know the theorem of Pocklington for proofing primality https://en.wikipedia.org/wiki/Pockli...primality_test Thanks in advance if you spend me some lines Bernhard 
20200814, 22:05  #2  
"Robert Gerbicz"
Oct 2005
Hungary
10111010001_{2} Posts 
Quote:
since rMp1=2*(2^(p1)1). Last fiddled with by R. Gerbicz on 20200814 at 22:07 

20200814, 22:13  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{2}·2,381 Posts 

20200816, 10:34  #4 
"Jeppe"
Jan 2016
Denmark
2^{3}·3·7 Posts 
Agree with Batalov; for proving primality of M_p, since the full factorization of M_p + 1 is trivial, we do not gain anything from the factorization of M_p  1.
Of course, it may be fun to find the factorization anyway; here is a factordb query for tiny examples. /JeppeSN 
20200816, 11:51  #5  
Jun 2003
2×3×853 Posts 
Quote:


20200817, 20:49  #6 
"Jeppe"
Jan 2016
Denmark
2^{3}·3·7 Posts 
Oops, that is right. It should have been 2^n2 for n prime, or 2*(2^(n1)  1). /JeppeSN

20210223, 14:32  #7  
Mar 2016
353 Posts 
A peaceful and pleasant day in spite of Covid19
Quote:
r odd and r  p1 then the factors f of Mp1 with f > p are f=1 mod r I was a little bit astonished about it. I have no explication for it. Perhaps someone could explain it to me and other members, interested in number theory. @Batalov: The factoring for Mp+1 is easy, sufficient for a proof and very nice, but perhaps the factoring of Mp1 gives some more details. 

20210223, 23:35  #9 
"Viliam FurÃk"
Jul 2018
Martin, Slovakia
3·7·31 Posts 

20210224, 02:31  #10 
Romulan Interpreter
Jun 2011
Thailand
2·3·5^{3}·13 Posts 
\(n=M_{1277}1 = 2^{1277}11 = 2^{1277}2 = 2*(2^{1276}1)\). That's a string of 1276 of 1, followed by a zero. 1276 is divisible by 2, 4, 11, 29. Therefore (by grouping the ones), n should be divisible by all factors of respective mersenne, i.e. 2 (from the last 0), 3 (from M2), 5 (from M4), 23, 89 (from M11), 233, 1103, 2089 (from M29). You can find plenty of combinations which are not true, actually, almost all where you "cross" them. In fact, you can say that the residue is 1 only when you don't cross them (i.e. 23 and 89 are 1 (mod 11), or 233, 1103 and 2089 are 1 (mod 29)), but that is a known property of mersenne factors
Last fiddled with by LaurV on 20210224 at 02:34 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
factorisation for p1, p is prime  bhelmes  Miscellaneous Math  31  20201009 08:22 
factorisation  devarajkandadai  Factoring  7  20130706 03:44 
Records for complete factorisation  BrianE  Math  25  20091216 21:40 
Being coy about a factorisation  fivemack  Math  7  20071117 01:27 
Kraitchik's factorisation method  Robertcop  Math  2  20060206 21:03 