mersenneforum.org Mn theorems +1 mod
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2021-03-12, 01:04   #12
Dr Sardonicus

Feb 2017
Nowhere

143608 Posts

Quote:
 Originally Posted by R. Gerbicz It is a perfect counterexample to your claim in the first post. Likely a=11 seems to be equally good just as a=3, maybe there is no other counterexample for a=11. Let me check [only the first few odd primes as base, ofcourse a=2 is not good]: Code: ? G(a)=forprime(p=2,2000,mp=2^p-1;if(Mod(a,mp)^((mp-1)/2)==Mod(-1,mp)&&isprime(mp)==0,print(p))) %19 = (a)->forprime(p=2,2000,mp=2^p-1;if(Mod(a,mp)^((mp-1)/2)==Mod(-1,mp)&&isprime(mp)==0,print(p))) ? G(3) ? G(5) ? G(7) ? G(11) 11 ? G(13) ? G(17) ? (tesing only p<2000).
This is going to miss cases when (a/Mp) = +1 if Mp is prime (which I'm guessing would be about half the cases for a given a > 3).

For example, (5/Mp) = +1 if Mp is prime and p == 1 (mod 4), but (5/Mp) = -1 if Mp is prime and p == 3 (mod 4). (IIRC this came up in a test devised by Lucas, but I'm too lazy to track it down.)

2021-03-12, 03:09   #13
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24·643 Posts

Quote:
 Originally Posted by Dr Sardonicus Could you please post one of these, or, if previously posted, give a link?
I remember discussions many years ago, but my memory is getting weak.... I mean I have a good memory but I don't remember exactly where I put it...

Long time ago I believed that mersenne factors behave in some similar way to fermat numbers (there are many reasons why that should be), and some similar "pepin test" would work for them (which is essentially a 3-PRP test), but I could not prove it. That would mean a 3-prp test, eventually with a "small tweak", could show if a cofactor is composite or not. Such "trick" would have been very useful and extremely valuable for our cofactoring ("disbelievers...") thread and people who do the PRP-CF work. Unfortunately, I was wrong, or just unable to find the "tweak". That's how we all learn...

Here is a discussion about rarity of PSP numbers (read following 3-4 posts too, before RDS jumped in and killed everybody ), and here is an example of a 3-PSP cofactor (i.e. it is 3-PRP, but still composite). There are not many of those, but they are enough. Some "didactic" implementation of a PSP-finder that also popped up with the search, and some may find it useful, is here (hey, don't jump to my head, it is didactic, i.e. to teach how it is done, not an optimized one!)

Edit: Here is another post which made it through the search filter. I would put it in a frame (the post, not the filter!) and stick it on a wall for the beginners who join the forum and ask the same questions again and again (HA! in the past I was more clever, and I had more patience, I totally forgot I was posting things like that on the forum )

Last fiddled with by LaurV on 2021-03-12 at 04:03

 2021-03-12, 08:16 #14 PAT291   Feb 2017 Belgium 3·7 Posts So thereexists no proof nor counterexample for a=3 yet? A proof is still possible? “If (3^(Mn-1)/2+ 1)==0 (mod Mn) then Mn is prime”. It may still be possible to prove this. And it's worthwhile If itstands, I believe it’s possible to speed up some calculations. If I read well there are still some "strong believers" to it
 2021-03-12, 11:28 #15 PAT291   Feb 2017 Belgium 3·7 Posts Now, I am trying to prove whether there exists some kind of induction for the Catalan sequence 3, 7, 127, … (if Ci divides 3^(Ci-1)/2 + 1==0 (mod Ci) for i=n,n+1,n+2 then it holds for i=n+3 or something like that) or a kind of maximum number of iterations f.e. 5. But I am not that strong with modulo calculations. I do notice some things running small macro’s. I believe there is no MMn when there’s a r
2021-03-12, 14:12   #16
Dr Sardonicus

Feb 2017
Nowhere

24·3·7·19 Posts

Quote:
 Originally Posted by LaurV Interesting enough, you can find small multiple-base-PSP very easy for small composite factors of mersenne numbers, for example 10974881 is both 2-PRP and 3-PRP, but it not a prime (it is a PSP product of 1913 and 5737, prime factors of M239).
Pepin's test works for Fermat numbers because if P = Fn the only prime factor of P - 1 is 2. If n > 0 and P is prime, 3 is a quadratic non-residue (mod P) so Mod(3,P)^((P-1)/2) = Mod(-1,P).

Conversely, if Mod(3, P)^((P-1)/2) = Mod(-1,P) then Mod(3,P) has multiplicative order exactly P-1, so P is prime.

The situation for Mersenne numbers is alas more complicated. We know that if p > 2 is prime, any prime factor q of 2^p - 1 is of the form q = 2*k*p + 1. This means that all the q-1 have the common factor 2*p, which is also a factor of any product of the q's minus 1. (As axn already noted back when) Since the exact multiplicative order of 2 (mod q) is always p, and p divides q-1 for every q, you can be sure that any product of the q's is a base-2 Fermat pseudoprime. It is also easy to see that any such product will "pass" the Euler test.

If we want a product of q's to be a base-3 Fermat pseudoprime, we want the lcm of the znorder(Mod(3, q)) to divide the product of the q's minus 1.

For the factors 1913 and 5737 of M239 (Thank you very much!) we have 1913 = 2*4*239 + 1 and 5737 = 2*12*239 + 1. The gcd of the q-1 values is 8*239.

It happens that znorder(Mod(3, 5737)) = 4*239, which guarantees n = 1913*5737 is a base-3 Fermat pseudoprime.

Note, however, that Mod(n,12) = Mod(5,12) so kronecker(3,n) == -1, but Mod(3,n)^((n-1)/2) == Mod(1, n) so the Euler test detects it as composite.

 2021-03-12, 16:04 #17 PAT291   Feb 2017 Belgium 3×7 Posts Thx. So 3^(M239-1)/2 == 1 (mod M239). It’s not a counterexample to my assumption?
2021-03-12, 17:00   #18
Dr Sardonicus

Feb 2017
Nowhere

24·3·7·19 Posts

Quote:
 Originally Posted by PAT291 Thx. So 3^(M239-1)/2 == 1 (mod M239). It’s not a counterexample to my assumption?
I didn't say that. I said that 3^((n-1)/2) == 1 (mod n) where n= 1913*5737 is a small composite factor of M239.

I suggest you stop responding to posts as if you hadn't read them.

2021-03-12, 17:50   #19
PAT291

Feb 2017
Belgium

258 Posts

Quote:
 Originally Posted by Dr Sardonicus I didn't say that. I said that 3^((n-1)/2) == 1 (mod n) where n= 1913*5737 is a small composite factor of M239. I suggest you stop responding to posts as if you hadn't read them.

Sorry if you take it that way. I didn’t catch the meaning of your post. I know about the q=2kp+1 and Pepin’s test for Fermat numbers.

I still believe “If (3^(Mn-1)/2 + 1)==0 (mod Mn)then Mn is prime” (Mn being a Mersenne number) is provable (and that I can proof it). If I read well the topics no proof or counterexample exists yet. So a proof is possible. But maybe I made an error somewhere or missed something that already exists.

 2021-03-12, 18:39 #20 PAT291   Feb 2017 Belgium 3·7 Posts Let me rephrase my original post. I claim that if (3^(Mn-1)/2 + 1)==0 (mod Mn) then Mn is prime. Mn being a Mersenne number. Maybe it holds also for other bases <> 3 (and 2).
 2021-03-12, 18:49 #21 PAT291   Feb 2017 Belgium 3×7 Posts I spend a lot of time trying to prove it. It was a big puzzle. A few weeks ago I believe to have found the last piece. Maybe I made a mistake along the way, that’s why I am very careful. Verification still has to be done. But is useless to verify if somebody tells it’s not possible or if there exists a counterexample. That means that I have to look for the error(s) … I am afraid, and nervous :-), I made an error somewhere after all …
2021-03-13, 14:00   #22
Dr Sardonicus

Feb 2017
Nowhere

24·3·7·19 Posts

Quote:
 Originally Posted by PAT291 I spend a lot of time trying to prove it. It was a big puzzle. A few weeks ago I believe to have found the last piece. Maybe I made a mistake along the way, that’s why I am very careful. Verification still has to be done. But is useless to verify if somebody tells it’s not possible or if there exists a counterexample. That means that I have to look for the error(s) … I am afraid, and nervous :-), I made an error somewhere after all …
Nobody said a proof was not possible. A number of people have pointed out that no proof is known. There is AFAIK no known composite Mp the test has failed to detect. There are however known composite factors of Mp's which are base-3 Fermat pseudoprimes.

I note that the 3-PRP test was probably not done on any Mp for which a prime factor q was found during initial factorization attempts. In such a case, it might be possible to prove that Mp is not a 3-PRP without actually running the test on Mp itself. If the multiplicative order of Mod(3,q) does not divide Mp - 1, then Mp is not a 3-PRP. (For example, 2^11 - 1 = 23*89, and the multiplicative order of Mod(3,89) is 88, which, being divisible by 4, does not divide 2^11 - 2.)

Recognizing the possibility of having made a mistake is a sign of maturity. If you want to know for sure, submit your argument to scrutiny by others. If your argument is wrong, acknowledge it, learn from it, and move on.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post jnml Miscellaneous Math 10 2019-04-21 15:33 ShiningArcanine Math 21 2012-04-27 01:38 fivemack Abstract Algebra & Algebraic Number Theory 10 2012-01-22 11:01 sghodeif Miscellaneous Math 18 2006-07-13 18:24

All times are UTC. The time now is 22:58.

Thu Jun 1 22:58:42 UTC 2023 up 287 days, 20:27, 0 users, load averages: 0.57, 0.86, 1.01

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔