mersenneforum.org is the factorisation of Mp-1 an advantage ?
 Register FAQ Search Today's Posts Mark Forums Read

 2020-08-14, 21:44 #1 bhelmes     Mar 2016 18C16 Posts is the factorisation of Mp-1 an advantage ? A peaceful and pleasant night for you, if I know the factorisation or a part of the factorisation of Mp-1 do I have any advantages for checking the primality ? (Mp should be a Mersenne number) Or in other words, is the factorisation of p-1 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
2020-08-14, 22:05   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,567 Posts

Quote:
 Originally Posted by bhelmes if I know the factorisation or a part of the factorisation of Mp-1 do I have any advantages for checking the primality ?
Probably there is no advantage for that, but any odd factor of Mp-1 could give a non-trival factor of another Mersenne number (with prime index),
since r|Mp-1=2*(2^(p-1)-1).

Last fiddled with by R. Gerbicz on 2020-08-14 at 22:07

2020-08-14, 22:13   #3
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

265D16 Posts

Quote:
 Originally Posted by bhelmes Or in other words, is the factorisation of Mp-1 helpful ?
N=Mp are a beautiful example of being proven with >>33.33% N+1 factorization (indeed, 100%).
Factorization of N-1 is needless, when you have a 100% N+1 factorization.

 2020-08-16, 10:34 #4 JeppeSN     "Jeppe" Jan 2016 Denmark 2608 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
2020-08-16, 11:51   #5
axn

Jun 2003

23×233 Posts

Quote:
 Originally Posted by JeppeSN Of course, it may be fun to find the factorization anyway; here is a factordb query for tiny examples.

2020-08-17, 20:49   #6
JeppeSN

"Jeppe"
Jan 2016
Denmark

2608 Posts

Quote:
 Originally Posted by axn You linked to Mp-2.
Oops, that is right. It should have been 2^n-2 for n prime, or 2*(2^(n-1) - 1). /JeppeSN

2021-02-23, 14:32   #7
bhelmes

Mar 2016

22·32·11 Posts

A peaceful and pleasant day in spite of Covid-19

Quote:
 Originally Posted by JeppeSN 2^n-2 for n prime
I noticed that the factors of Mp-1 have the following proporty:
r odd and r | p-1 then the factors f of Mp-1 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 Mp-1 gives some more details.

 2021-02-23, 16:58 #8 Nick     Dec 2012 The Netherlands 6DF16 Posts See the exercise here
2021-02-23, 23:35   #9
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

2F116 Posts

Quote:
 Originally Posted by bhelmes I noticed that the factors of Mp-1 have the following proporty: r odd and r | p-1 then the factors f of Mp-1 with f > p are f=1 mod r
Not quite. M1277-1 has a factor of 2089, among others. 1277-1 is divisible by 11. 2089 is 10 (mod 11), not 1.

 2021-02-24, 02:31 #10 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 7×1,423 Posts $$n=M_{1277}-1 = 2^{1277}-1-1 = 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 2021-02-24 at 02:34

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Miscellaneous Math 31 2020-10-09 08:22 devarajkandadai Factoring 7 2013-07-06 03:44 Brian-E Math 25 2009-12-16 21:40 fivemack Math 7 2007-11-17 01:27 Robertcop Math 2 2006-02-06 21:03

All times are UTC. The time now is 01:20.

Thu May 19 01:20:39 UTC 2022 up 34 days, 23:21, 0 users, load averages: 1.36, 1.60, 1.78