Amazing pattern with -12 (was -3) - Page 3

paulunderwood · 2022-11-27, 16:47

As with "-12" (GCD-less probably because the discriminant of at r=znorder(Mod(-12,n)) is 1+48, a square) compared to "12", and comparing "-3" to "3" -- the latter needing GCD depending on whether n is 1 or 3 mod 4 -- the same can be said about "-2". This seems only to need a check for gcd(2*r-1,n-1)==1.

It is all confusing, but it seems some (positive?) values need either a check of gcd(r-1,n-1)==1 or gcd(2*r-1,n-1)==1 depending on n%4.; The negative values require at most one GCD check be that 2*r-1 as with "-2" or r-1 as with "-3".

What am taking about? Working over the equation x^2-b^r*x+b = 0.

paulunderwood · 2022-12-13, 21:07

Having read the paper attached to this thread earlier, rather than considering (-3)^(4*(r-1))-1 if we consider (-3)^(2*(r-1))+1 -- the predecessor -- we have (-3)^(2*(r-1)) == -1 mod n. But then multiplicative order of -3 mod n called z must be even and (-3)^(z/2) == -1 mod n. Therefore (-3)^(2*(r-1)) == (-3)^(z/2) mod n. If 1<=r<=z then 4*(r-1) = z (**). But z | n-1 and we have already stipulated that gcd(r-1,n-1)==1. So gcd(r-1,z)==1. Thus (**) is impossible.

Is this a proof of a lemma?

RMLabrador · 2022-12-13, 21:54

sorry silly me (i'm lost the point, here in Ukraine now is the real AC/DC problem))), we still talk about something for pseudoprimes only or else?

paulunderwood · 2022-12-13, 21:59

Quote:

Originally Posted by RMLabrador

sorry silly me (i'm lost the point, here in Ukraine now is the real AC/DC problem))), we still talk about something for pseudoprimes only or else?

Pseudoprimes for now, but hopefully leading to a prime test. If the argument just given is valid, then it is one step in the right direction.

RMLabrador · 2022-12-13, 22:19

I remember, I mumbled something about tree, so pseudoprime is a tree, an average tree, there is nothing special in them - their existence is only flaws in out primality test; take the true test - and we have NO pseudiprimes, and what are we suppose to do now?

paulunderwood · 2022-12-13, 22:29

Quote:

Originally Posted by RMLabrador

I remember, I mumbled something about tree, so pseudoprime is a tree, an average tree, there is nothing special in them - their existence is only flaws in out primality test; take the true test - and we have NO pseudiprimes, and what are we suppose to do now?

Even a large tree starts out as a small one. A pseudoprime test that has no known counterexample for all parameters for n<2*10^12 (on a Celeron core); A test that may well turn out to be a revolutionary primality test. Instead of months on mullticore systems, a *proof* in minutes on one core! But I need someone to check over my lemma given above, before proceeding to a fully fledged proof attempt.

RMLabrador · 2022-12-13, 23:15

You know, the Solar core of our Sun, have a temperatures of 10 up to 15 million kelvins +- a few millions)))
Here the diff btw mathematican&astronomer
For me, the One Million Kelvins diff is OK
The wierld mathmans from mersenneforums never say this
and proof seems unlikely, sorry
((Every time using mod() (in prime test or so) we just like Moses&water from stone
Sweet, but grave sin))

paulunderwood · 2022-12-14, 02:31

Quote:

Originally Posted by RMLabrador

You know, the Solar core of our Sun, have a temperatures of 10 up to 15 million kelvins +- a few millions)))
Here the diff btw mathematican&astronomer
For me, the One Million Kelvins diff is OK
The wierld mathmans from mersenneforums never say this
and proof seems unlikely, sorry
((Every time using mod() (in prime test or so) we just like Moses&water from stone
Sweet, but grave sin))

Instead of hand-waving and saying it just can't be true because mathematicians would find the truth of my argument unlikely, please pin point the error in the argument I gave in post #24.

Here is another argument. From the test we know (-3)^(n-1) == 1 mod n. We know (-3)^z == 1 mod n by definition. If (-3)^(4*(n-1)) == 1 mod n, then z | n-1 and z | 4*(r-1), but we have taken gcd(r-1,n-1) = 1. So z | 4. I.e. 80 == 0 mod n. So n must be 5. Where is flaw in this simpler argument?

Andrew Usher · 2022-12-17, 16:34

Any proposed deterministic primality test absolutely requires a proof! If you don't know the different between a deterministic and a probable prime test (the latter of which we already have well enough) then you probably aren't going to be making a contribution.

There isn't only one method of proof as the LL test shows. But some proof is necessary, not just checking that known primes satisfy it. Even if you also proved that all _composites_ up to a large limit failed the test, it wouldn't count as a proof.

Such a primality proof would likely represent a significant breakthrough especially since it could probably be extended to other repunits and repunit-like numbers.

paulunderwood · 2022-12-18, 05:08

Consider working over x^2-3^r*x+3 (**) We want gcd(r-1,n-1)=1 as stated earlier. We also know the multiplicative order z (of 3 mod n) is even and 3^(z/2)==-1 mod n.

Now x^2-3^(z/2)*3+3=0 is x^2+3*x+3=0. This is the same as (**) if we are taking (n+1)th powers of x over it.

I claim there are only pseudoprimes for r=1 and r=z/2+1, both of which can be eliminated by taking gcd(r-1,n-1)=1.

Here is code that I a am running:

Code:

{b=3;forstep(n=3,1000000000000,2,
if(gcd(b,n)==1&&!ispseudoprime(n)&&Mod(b,n)^((n-1)/2)==kronecker(b,n),
z=znorder(Mod(b,n));if(z%2==0&&Mod(b,n)^(z/2)==-1,
for(r=1,z/2,
D=lift(Mod(b,n)^(2*r)-4*b);
if(kronecker(D,n)==-1&&Mod(Mod(x,n),x^2-(Mod(b,n)^(2*r-1)-2)*x+1)^((n+1)/2)==kronecker(b,n),
g=gcd(r-1,n-1);print([n,b,z,r,g]))))));}

The above claim is not quite right as I get output:

Code:

[28027505969, 3, 4048, 1, 28027505968]                        
[28027505969, 3, 4048, 1233, 1232]

Some more thinking is needed!

I note z*k+1=p for some k where prime p | n. For all prime p_i | n for various k_i?

Andrew Usher · 2022-12-18, 15:00

How did my last post end up here? It was posted only to the Wagstaff forum, in reply to 'primality test' proposals that apparently dominate that forum.

Still, it seems almost appropriate here, because you also don't seem to appreciate the need for a proof. People generally aren't interested in another PRP test, as we already have adequate ones (for very large numbers, time is the crucial factor, and the simple Fermat (or strong Fermat) test is faster than any other). You can't just hand wave 'this can probably be converted to a deterministic test'; you need to at least try to outline a proof, and no amount of computation gets any closer to doing that.

2022-11-27, 16:47	#23
paulunderwood Sep 2002 Database er0rr 7·23·29 Posts	As with "-12" (GCD-less probably because the discriminant of at r=znorder(Mod(-12,n)) is 1+48, a square) compared to "12", and comparing "-3" to "3" -- the latter needing GCD depending on whether n is 1 or 3 mod 4 -- the same can be said about "-2". This seems only to need a check for gcd(2r-1,n-1)==1. It is all confusing, but it seems some (positive?) values need either a check of gcd(r-1,n-1)==1 or gcd(2r-1,n-1)==1 depending on n%4.; The negative values require at most one GCD check be that 2r-1 as with "-2" or r-1 as with "-3". What am taking about? Working over the equation x^2-b^rx+b = 0. Last fiddled with by paulunderwood on 2022-11-27 at 16:47

2022-12-17, 16:34	#31
Andrew Usher Dec 2022 1B8₁₆ Posts	Amazing pattern with -12 (was -3) Any proposed deterministic primality test absolutely requires a proof! If you don't know the different between a deterministic and a probable prime test (the latter of which we already have well enough) then you probably aren't going to be making a contribution. There isn't only one method of proof as the LL test shows. But some proof is necessary, not just checking that known primes satisfy it. Even if you also proved that all _composites_ up to a large limit failed the test, it wouldn't count as a proof. Such a primality proof would likely represent a significant breakthrough especially since it could probably be extended to other repunits and repunit-like numbers.

2022-12-18, 05:08	#32
paulunderwood Sep 2002 Database er0rr 123D₁₆ Posts	The case for 3 Consider working over x^2-3^rx+3 () We want gcd(r-1,n-1)=1 as stated earlier. We also know the multiplicative order z (of 3 mod n) is even and 3^(z/2)==-1 mod n. Now x^2-3^(z/2)3+3=0 is x^2+3x+3=0. This is the same as () if we are taking (n+1)th powers of x over it. I claim there are only pseudoprimes for r=1 and r=z/2+1, both of which can be eliminated by taking gcd(r-1,n-1)=1. Here is code that I a am running: Code: {b=3;forstep(n=3,1000000000000,2, if(gcd(b,n)==1&&!ispseudoprime(n)&&Mod(b,n)^((n-1)/2)==kronecker(b,n), z=znorder(Mod(b,n));if(z%2==0&&Mod(b,n)^(z/2)==-1, for(r=1,z/2, D=lift(Mod(b,n)^(2r)-4b); if(kronecker(D,n)==-1&&Mod(Mod(x,n),x^2-(Mod(b,n)^(2r-1)-2)x+1)^((n+1)/2)==kronecker(b,n), g=gcd(r-1,n-1);print([n,b,z,r,g]))))));} The above claim is not quite right as I get output: Code: [28027505969, 3, 4048, 1, 28027505968] [28027505969, 3, 4048, 1233, 1232] Some more thinking is needed! I note zk+1=p for some k where prime p \| n. For all prime p_i \| n for various k_i? Last fiddled with by paulunderwood on 2022-12-18 at 06:53

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Amazing 6	paulunderwood	Miscellaneous Math	118	2021-03-18 21:53
Amazing result in P-1	Miszka	Information & Answers	2	2014-07-04 17:11
Amazing academic resource	Xyzzy	Lounge	6	2012-03-25 22:57
Amazing!!!	R.D. Silverman	Factoring	5	2006-01-26 09:14
Two Amazing Things	clowns789	Hardware	1	2003-12-27 16:57

2022-12-13, 21:07	#24
paulunderwood Sep 2002 Database er0rr 7·23·29 Posts	Another attempted proof Having read the paper attached to this thread earlier, rather than considering (-3)^(4(r-1))-1 if we consider (-3)^(2(r-1))+1 -- the predecessor -- we have (-3)^(2(r-1)) == -1 mod n. But then multiplicative order of -3 mod n called z must be even and (-3)^(z/2) == -1 mod n. Therefore (-3)^(2(r-1)) == (-3)^(z/2) mod n. If 1<=r<=z then 4(r-1) = z (). But z \| n-1 and we have already stipulated that gcd(r-1,n-1)==1. So gcd(r-1,z)==1. Thus () is impossible. Is this a proof of a lemma? Last fiddled with by paulunderwood on 2022-12-13 at 21:18*

2022-12-13, 21:54	#25
RMLabrador "Chereztynnoguzakidai" Oct 2022 Ukraine, near Kyiv. 3·19 Posts	sorry silly me (i'm lost the point, here in Ukraine now is the real AC/DC problem))), we still talk about something for pseudoprimes only or else?

2022-12-13, 22:19	#27
RMLabrador "Chereztynnoguzakidai" Oct 2022 Ukraine, near Kyiv. 3·19 Posts	I remember, I mumbled something about tree, so pseudoprime is a tree, an average tree, there is nothing special in them - their existence is only flaws in out primality test; take the true test - and we have NO pseudiprimes, and what are we suppose to do now?

2022-12-13, 23:15	#29
RMLabrador "Chereztynnoguzakidai" Oct 2022 Ukraine, near Kyiv. 3×19 Posts	You know, the Solar core of our Sun, have a temperatures of 10 up to 15 million kelvins +- a few millions))) Here the diff btw mathematican&astronomer For me, the One Million Kelvins diff is OK The wierld mathmans from mersenneforums never say this and proof seems unlikely, sorry ((Every time using mod() (in prime test or so) we just like Moses&water from stone Sweet, but grave sin))

2022-12-18, 15:00	#33
Andrew Usher Dec 2022 2³×5×11 Posts	How did my last post end up here? It was posted only to the Wagstaff forum, in reply to 'primality test' proposals that apparently dominate that forum. Still, it seems almost appropriate here, because you also don't seem to appreciate the need for a proof. People generally aren't interested in another PRP test, as we already have adequate ones (for very large numbers, time is the crucial factor, and the simple Fermat (or strong Fermat) test is faster than any other). You can't just hand wave 'this can probably be converted to a deterministic test'; you need to at least try to outline a proof, and no amount of computation gets any closer to doing that.