 mersenneforum.org Mn theorems +1 mod
 Register FAQ Search Today's Posts Mark Forums Read  2021-03-11, 12:05 #1 PAT291   Feb 2017 Belgium 2110 Posts Mn theorems +1 mod Is there any theorem that says that if Mn divides (a^(n-1)/2 + 1) for some a > 2 then Mn is prime? Where can I find related theorems. Thanks in advance   2021-03-11, 13:16 #2 axn   Jun 2003 125248 Posts Assuming that you meant to write a^(Mn-1)/2 + 1, have a look at https://en.wikipedia.org/wiki/Euler_pseudoprime   2021-03-11, 13:54 #3 PAT291   Feb 2017 Belgium 3×7 Posts Thanks. I wasalready given some information about pseudoprimes. Indeed sometimes they weretalking about pseudoprimes. It was always one direction. Apparently it's also the case for Eulerpseudoprimes. If I amcorrect there exists no such theorem (as stated above). Is that true? My nextquestion. If somebody can proof that, under some conditions, the above holds,can it be helpful in calculations? Would it be interesting for this forum?   2021-03-11, 14:58 #4 Dr Sardonicus   Feb 2017 Nowhere 24·3·7·19 Posts A specific instance has been discussed previously in this Forum, in, e.g. this thread. If P is prime, and gcd(a, P) == 1 then a^((P-1)/2) == (a/P) (mod P) [quadratic character; 1 if a is a quadratic residue mod P, -1 if not]. Multiplying through by "a" gives a convenient formula for a square root of a quadratic residue if P == 3 (mod 4). It also gives an especially convenient exponent if P = Mp = 2^p - 1. If p > 2 and Mp = P is prime, 3 is a quadratic non-residue (mod P). We then have the familiar 3-PRP test If p > 2 is prime, and Mod(3, 2^p - 1)^(2^(p-1)) + 3 <> Mod(0, 2^p - 1), then 2^p - 1 is composite. If equality holds, it is possible AFAIK that 2^p - 1 could still be composite, so an LL test would be required to be certain. I am not aware of any examples where the 3-PRP fails to detect a composite Mp.   2021-03-11, 15:05   #5
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24×643 Posts Quote:
 Originally Posted by Dr Sardonicus I am not aware of any examples where the 3-PRP fails to detect a composite Mp.
Albeit they are possible in theory (i.e. there is no proof of the contrary, and if they exist, they are called "pseudoprimes"), you would be more famous if you find one such pseudoprime, than if you find a 1 billion digits mersenne prime. Please note that when talking about composite mersenne factors, there are few known which are pseudoprime. It was my "belief" in the past that they do not exist (so a 3-prp would be enough to decide if a cofactor is prime or composite), but I could not prove it, and later a forumite here provided me with counterexamples. Thinking by extrapolation, a composite mersenne is just a product of prime mersenne factors (similar to a composite cofactor), so there is no reason why some of them would not be 3-pseudoprimes.

Last fiddled with by LaurV on 2021-03-11 at 15:11   2021-03-11, 16:16   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×19×43 Posts Quote:
 Originally Posted by PAT291 Is there any theorem that says that if Mn divides (a^(n-1)/2 + 1) for some a > 2 then Mn is prime? Where can I find related theorems. Thanks in advance
So you want to say that if a^((mp-1)/2)==-1 mod mp for given a>2 then mp is prime.
It would follow that Mp is always prime(!), just use a=-1+mp. To see a non-trivial counterexample: let a=11 and p=11 then your equation holds, but m11=23*89 is composite.   2021-03-11, 16:40   #7
Dr Sardonicus

Feb 2017
Nowhere

24·3·7·19 Posts Quote:
 Originally Posted by LaurV Please note that when talking about composite mersenne factors, there are few known which are pseudoprime. It was my "belief" in the past that they do not exist (so a 3-prp would be enough to decide if a cofactor is prime or composite), but I could not prove it, and later a forumite here provided me with counterexamples.
Could you please post one of these, or, if previously posted, give a link?

I can only imagine the fun that would ensue if

Mod(3, 2^p - 1)^(2^(p-1)) + 3 == Mod(0, 2^p -1) but

LL test says 2^p - 1 is composite.   2021-03-11, 16:50   #8
PAT291

Feb 2017
Belgium

2110 Posts Quote:
 Originally Posted by R. Gerbicz So you want to say that if a^((mp-1)/2)==-1 mod mp for given a>2 then mp is prime. It would follow that Mp is always prime(!), just use a=-1+mp. To see a non-trivial counterexample: let a=11 and p=11 then your equation holds, but m11=23*89 is composite.

11 seems not a good 'a'. 3 seems a candidate. If I read well, there's no counterexemple for the 3-PRP test for Mn numbers   2021-03-11, 17:14   #9
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·19·43 Posts Quote:
 Originally Posted by PAT291 11 seems not a good 'a'. 3 seems a candidate. If I read well, there's no counterexemple for the 3-PRP test for Mn numbers
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).   2021-03-11, 18:40   #10
PAT291

Feb 2017
Belgium

3·7 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).

sorry, I believe it's true for a=3 and was looking for some theorems or whether there existed already some proof. At the same time I wondered if it was maybe true for other a.

thanks for the quick reaction

Last fiddled with by PAT291 on 2021-03-11 at 19:19   2021-03-11, 19:31   #11
paulunderwood

Sep 2002
Database er0rr

7·23·29 Posts Quote:
 Originally Posted by PAT291 sorry, I believe it's true for a=3 and was looking for some theorems or whether there existed already some proof. At the same time I wondered if it was maybe true for other a. thanks for the quick reaction
3 is special because kronecker(3,Mp)==-1 for all odd p.

Lehmer's test is an efficient implementation of Mod(Mod(x+2,Mp),x^2-3)^2^p==1

Last fiddled with by paulunderwood on 2021-03-11 at 19:48   Thread Tools Show Printable Version Email this Page 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:00.

Thu Jun 1 22:00:12 UTC 2023 up 287 days, 19:28, 0 users, load averages: 1.87, 1.14, 0.99 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.

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