mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Combinatorics & Combinatorial Number Theory

Reply
 
Thread Tools
Old 2020-08-14, 21:44   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32·41 Posts
Default 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
bhelmes is offline   Reply With Quote
Old 2020-08-14, 22:05   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·3·11·23 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2020-08-14, 22:13   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

226168 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
Batalov is offline   Reply With Quote
Old 2020-08-16, 10:34   #4
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

52·7 Posts
Default

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
JeppeSN is offline   Reply With Quote
Old 2020-08-16, 11:51   #5
axn
 
axn's Avatar
 
Jun 2003

5,179 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
Of course, it may be fun to find the factorization anyway; here is a factordb query for tiny examples.
You linked to Mp-2.
axn is offline   Reply With Quote
Old 2020-08-17, 20:49   #6
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

52·7 Posts
Red face

Quote:
Originally Posted by axn View Post
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
JeppeSN is offline   Reply With Quote
Old 2021-02-23, 14:32   #7
bhelmes
 
bhelmes's Avatar
 
Mar 2016

17116 Posts
Default

A peaceful and pleasant day in spite of Covid-19

Quote:
Originally Posted by JeppeSN View Post
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.
bhelmes is offline   Reply With Quote
Old 2021-02-23, 16:58   #8
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

33368 Posts
Default

See the exercise here
Nick is offline   Reply With Quote
Old 2021-02-23, 23:35   #9
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

13028 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
Viliam Furik is offline   Reply With Quote
Old 2021-02-24, 02:31   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24×613 Posts
Default

\(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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factorisation for p-1, p is prime bhelmes Miscellaneous Math 31 2020-10-09 08:22
factorisation devarajkandadai Factoring 7 2013-07-06 03:44
Records for complete factorisation Brian-E Math 25 2009-12-16 21:40
Being coy about a factorisation fivemack Math 7 2007-11-17 01:27
Kraitchik's factorisation method Robertcop Math 2 2006-02-06 21:03

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


Tue Nov 30 06:01:35 UTC 2021 up 130 days, 30 mins, 0 users, load averages: 1.08, 1.10, 1.10

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