MM127 - Page 3

science_man_88 · 2015-05-11, 00:27

Quote:

Originally Posted by Batalov

I might as well bury myself I'm useless either way at this point.

ewmayer · 2015-05-11, 01:03

Quote:

Originally Posted by ATH

But k is not always 4n+1. For example the factor 45315868721 of the exponent 566448359 I linked:
45315868721 = 2*40*566448359 + 1, so k=40 which is not 4n+1, and several of the other factors of that exponent does not fit k=4n+1 either.

In fact the only k's that never work for any prime exponent p are of the form k=4n+2, because those leads to factors 2kp+1 which is not +/1 (mod 8).

This is true even if we take into account the various relevant residue classes of the exponent in question: e.g. for MM31 and MM127 both exponents == 7 (mod 60). Looking at the table my TF code uses, this value of p%60 permits factors with k%60 = 0,5,8,9,12,17,20,24,29,32,33,44,45,48,53,57, which have k%4 = 0 or 1. And in fact the 4 known factors of MM31 have k = 68745, 20269004, 56474845800 and 41448832329225, i.e. we have 2 factors with each possible (mod 4) value.

#Fail

Zeta-Flux · 2015-05-11, 03:19

Stan,

Consider the following example.

Let $p=47$ , which is prime. We see that $2\cdot p+1=95=5\cdot 19$ is composite. Also $M_p=2^{47}-1=2351\cdot 4513\cdot 13264529$ is composite.

Next, the smallest $\lambda$ such that $2(4\lambda+1)p+1$ is prime is $\lambda=3$ which gives $8\lambda p+2p+1=1123$ . This prime does not divide $M_p$ .

The problem in your file seems to come right near the end. There is no justification for the claim that $8\mu+2$ divides $8\lambda+2$ . Everything else seemed okay (modulo minor mistakes). Sorry this didn't work out!

Now let me give you some advice. The first example where $p$ is prime, $2p+1$ is composite, and $M_p$ is composite is when $p=43$ . It looks like you examined this case. But the very next case, when $p=47$ fails. In the future I recommend looking at multiple cases. (By the way, I also checked the next two cases $p=59,67$ , and they also fail.)

Sincerely,
Pace

axn · 2015-05-11, 03:34

Quote:

Originally Posted by Stan

Please supply a counterexample with k = 4n + 1 and I will have to think again.

p=47 is the first counterexample.
1223 is smallest prime of the form 2kp+1 = 7 (mod 8). k=13, lambda=3. However, it doesn't divide. The actual smallest prime of that form that does divide M(p) is 2351 (k=25, mu=6).

Code:

find_counter_example(p)=for(k=1,100, f=(8*k+2)*p+1; if(isprime(f), if(Mod(2,f)^p!=1, print("Counter example ", p, ":", k)); return));

forprime(p=3, 1001, if(p%4==3 && !isprime(2*p+1) && !isprime(2^p-1), find_counter_example(p)))

ATH · 2015-05-11, 05:49

Quote:

Originally Posted by ewmayer

This is true even if we take into account the various relevant residue classes of the exponent in question: e.g. for MM31 and MM127 both exponents == 7 (mod 60). Looking at the table my TF code uses, this value of p%60 permits factors with k%60 = 0,5,8,9,12,17,20,24,29,32,33,44,45,48,53,57, which have k%4 = 0 or 1. And in fact the 4 known factors of MM31 have k = 68745, 20269004, 56474845800 and 41448832329225, i.e. we have 2 factors with each possible (mod 4) value.

#Fail

Yeah, I know. It is true for +/-1,+/-7,+/-17,+/-23,+/-31,+/-41,+/-47,+/-49 (mod 120) but I did not want to start explaining that, so I just wrote +/- 1 (mod 8).

Stan · 2015-06-18, 20:23

Many thanks axn, your pari program has, I think, found a factor of MM127 and therefore MM127 is composite. Could you please check the validity of the program and let me know what you think.
The program is:
find_example(p)=for(k=1,100,q=(8*k+2)*p+1;if(isprime(q),if(Mod(2,q)^p=1,print("Example ",q," : ",k));
p=2^127-1;find_example(p)
The program gives k = 14, q = 19396094914493492417412352623610788052879.
If it is correct, MM₁₂₇ has the factor q.

legendarymudkip · 2015-06-18, 20:49

Quote:

Originally Posted by Stan

Many thanks axn, your pari program has, I think, found a factor of MM127 and therefore MM127 is composite. Could you please check the validity of the program and let me know what you think.
The program is:
find_example(p)=for(k=1,100,q=(8*k+2)*p+1;if(isprime(q),if(Mod(2,q)^p=1,print("Example ",q," : ",k));
p=2^127-1;find_example(p)
The program gives k = 14, q = 19396094914493492417412352623610788052879.
If it is correct, MM₁₂₇ has the factor q.

2^2[SUP]127-1[/SUP]-1 mod 19396094914493492417412352623610788052879 is 12878846122774700542942977398640678236037, so no, it's not a factor.

Stan · 2015-06-18, 21:04

Quote:

Originally Posted by legendarymudkip

2^2[SUP]127-1[/SUP]-1 mod 19396094914493492417412352623610788052879 is 12878846122774700542942977398640678236037, so no, it's not a factor.

Then why does the pari program give 2^2[SUP]127-1[/SUP]=1 mod 19396094914493492417412352623610788052879?

science_man_88 · 2015-06-18, 21:07

Quote:

Originally Posted by Stan

Many thanks axn, your pari program has, I think, found a factor of MM127 and therefore MM127 is composite. Could you please check the validity of the program and let me know what you think.
The program is:
find_example(p)=for(k=1,100,q=(8*k+2)*p+1;if(isprime(q),if(Mod(2,q)^p=1,print("Example ",q," : ",k));
p=2^127-1;find_example(p)
The program gives k = 14, q = 19396094914493492417412352623610788052879.
If it is correct, MM₁₂₇ has the factor q.

the code they gave you finds times your idea about the first prime of form 2*(4k+1)*p+1 dividing Mp doesn't work. the number you think is a factor is prime but does not divide MM127. it actually uses not equals though I didn't realize this either until after I ran it.

legendarymudkip · 2015-06-18, 21:31

Quote:

Originally Posted by Stan

Then why does the pari program give 2^2[SUP]127-1[/SUP]=1 mod 19396094914493492417412352623610788052879?

I'm not sure if it's the same in pari, but the "if(Mod(2,q)^p=1" seems to not be comparing for equality, but rather attempting an assignment, because of the use of = instead of ==. (I've never used pari so I don't know if it uses those operators to mean the same things) One thing that's certain is that it's not running Mod(2,q)^p, since 2 mod q is 2, and 2^p has 2^127-1 bits, or roughly 2^44 yottabytes of data, which exceeds all memory capacities at the moment. If it's using modular multiplication for every step I'm not sure what's going wrong. What does a print of Mod(2,q)^p give?

science_man_88 · 2015-06-18, 21:44

Quote:

Originally Posted by legendarymudkip

I'm not sure if it's the same in pari, but the "if(Mod(2,q)^p=1" seems to not be comparing for equality, but rather attempting an assignment, because of the use of = instead of ==. (I've never used pari so I don't know if it uses those operators to mean the same things) One thing that's certain is that it's not running Mod(2,q)^p, since 2 mod q is 2, and 2^p has 2^127-1 bits, or roughly 2^44 yottabytes of data, which exceeds all memory capacities at the moment. If it's using modular multiplication for every step I'm not sure what's going wrong. What does a print of Mod(2,q)^p give?

you're correct From GP 2.7.3:

Code:

(18:16) gp > ??===
Comparison and Boolean operators:

   The six standard comparison operators <= , < , >= , > , == , != are available in GP.  The result is 1 if the comparison is true, 0 if it is false.  The operator == is quite liberal : for instance,
the integer 0, a 0 polynomial, and a vector with 0 entries are all tested equal.

   The extra operator === tests whether two objects are identical and is much stricter than == : objects of different type or length are never identical.

   For the purpose of comparison, t_STR objects are strictly larger than any other non-string type; two t_STR objects are compared using the standard lexicographic order.

   GP accepts < > as a synonym for != . On the other hand, = is definitely not a synonym for == : it is the assignment statement.

   The standard boolean operators || (inclusive or), && (and) and ! (not) are also available.

2015-05-11, 03:19	#25
Zeta-Flux May 2003 60B₁₆ Posts	Stan, Consider the following example. Let $p=47$ , which is prime. We see that $2\cdot p+1=95=5\cdot 19$ is composite. Also $M_p=2^{47}-1=2351\cdot 4513\cdot 13264529$ is composite. Next, the smallest $\lambda$ such that $2(4\lambda+1)p+1$ is prime is $\lambda=3$ which gives $8\lambda p+2p+1=1123$ . This prime does not divide $M_p$ . The problem in your file seems to come right near the end. There is no justification for the claim that $8\mu+2$ divides $8\lambda+2$ . Everything else seemed okay (modulo minor mistakes). Sorry this didn't work out! Now let me give you some advice. The first example where $p$ is prime, $2p+1$ is composite, and $M_p$ is composite is when $p=43$ . It looks like you examined this case. But the very next case, when $p=47$ fails. In the future I recommend looking at multiple cases. (By the way, I also checked the next two cases $p=59,67$ , and they also fail.) Sincerely, Pace Last fiddled with by Zeta-Flux on 2015-05-11 at 03:21

2015-06-18, 20:23	#28
Stan Dec 2011 44₈ Posts	Many thanks axn, your pari program has, I think, found a factor of MM127 and therefore MM127 is composite. Could you please check the validity of the program and let me know what you think. The program is: find_example(p)=for(k=1,100,q=(8k+2)p+1;if(isprime(q),if(Mod(2,q)^p=1,print("Example ",q," : ",k)); p=2^127-1;find_example(p) The program gives k = 14, q = 19396094914493492417412352623610788052879. If it is correct, MM₁₂₇ has the factor q. Last fiddled with by Stan on 2015-06-18 at 20:56 Reason: program missing

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Is MM127 a PRP?	aketilander	Operazione Doppi Mersennes	6	2012-10-31 16:02
MM127	antimath	Lone Mersenne Hunters	12	2012-01-11 03:46
MM127	Dougal	LMH > 100M	26	2009-12-13 09:57
Is MM127 Prime? Just a Poll	jinydu	Miscellaneous Math	57	2008-11-08 17:48
MM127 Checkout Page	clowns789	Lone Mersenne Hunters	44	2004-09-30 08:06