mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > carpetpool

Reply
 
Thread Tools
Old 2020-03-01, 17:52   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22·79 Posts
Post Patterns in primes (no counterexamples)

Lemma: Let D = a^2+4 and p be a prime such that Jacobi(D | p) = -1.

Then
(x^2 + a*x - 1)^p = x^3 - x^2 + (a^2 + 2)*x - a^2 - 5 mod(p, x^4+D*x^2+D)
Or
(x^2 - a*x - 1)^p = x^3 - x^2 + (a^2 + 2)*x - a^2 - 5 mod(p, x^4+D*x^2+D)

For instance, if D = 5, (a = ±1), then (a=1 if p = 3 mod 5) and (a = -1 if p = 2 mod 5).
Also found were,

D = 8, (a = ±2), then (a=2 if p = {11, 13} mod 16) and (a = -2 if p = {3, 5} mod 16)
D = 13, (a = ±3), then (a=3 if p = {2, 5, 6} mod 13) and (a = -3 if p = {7, 8, 11} mod 13)
D = 20, (a = ±4), then (a=4 if p = {3, 7, 13, 17} mod 40) and (a = -4 if p = {23, 27, 33, 37} mod 40)
... (and so on)

The question here is what is the general pattern for determining which property will hold (the first one or second one)?

What makes this test interesting is the primes in the same groups and residue classes mod D behave differently for this test.

For instance, there is no polynomial which is irreducible for primes p = 2 mod 5 but not for primes p = 3 mod 5, or vice versa.

Last fiddled with by carpetpool on 2020-03-01 at 20:33 Reason: Typo error, (thanks to paulunderwood for noticing).
carpetpool is offline   Reply With Quote
Old 2020-03-01, 18:26   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,449 Posts
Default

Quote:
Originally Posted by carpetpool View Post
Lemma: Let D = a^2+4 and p be a prime such that Jacobi(a | p) = -1.

Then
(x^2 + a*x - 1)^p = x^3 - x^2 + (a^2 + 2)*x - a^2 - 5 mod(p, x^4+D*x^2+D)
Or
(x^2 - a*x - 1)^p = x^3 - x^2 + (a^2 + 2)*x - a^2 - 5 mod(p, x^4+D*x^2+D)

For instance, if D = 5, (a = ±1), then (a=1 if p = 3 mod 5) and (a = -1 if p = 2 mod 5).
Also found were,

D = 8, (a = ±2), then (a=2 if p = {11, 13} mod 16) and (a = -2 if p = {3, 5} mod 16)
D = 13, (a = ±3), then (a=3 if p = {2, 5, 6} mod 13) and (a = -3 if p = {7, 8, 11} mod 13)
D = 20, (a = ±4), then (a=4 if p = {3, 7, 13, 17} mod 40) and (a = -4 if p = {23, 27, 33, 37} mod 40)
... (and so on)

The question here is what is the general pattern for determining which property will hold (the first one or second one)?

What makes this test interesting is the primes in the same groups and residue classes mod D behave differently for this test.

For instance, there is no polynomial which is irreducible for primes p = 2 mod 5 but not for primes p = 3 mod 5, or vice versa.
Code:
? a=5;D=a^2+4;p=107;Mod(Mod(1,p)*x^2-a*x-1,x^4+D*x^2+D)^p==x^3-x^2+(a^2+2)*x-a^2-5
0
? a=5;D=a^2+4;p=107;Mod(Mod(1,p)*x^2+a*x-1,x^4+D*x^2+D)^p==x^3-x^2+(a^2+2)*x-a^2-5
0
? kronecker(a,p)
-1
paulunderwood is offline   Reply With Quote
Old 2020-03-01, 20:43   #3
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22×79 Posts
Post

Quote:
Originally Posted by paulunderwood View Post
Code:
? a=5;D=a^2+4;p=107;Mod(Mod(1,p)*x^2-a*x-1,x^4+D*x^2+D)^p==x^3-x^2+(a^2+2)*x-a^2-5
0
? a=5;D=a^2+4;p=107;Mod(Mod(1,p)*x^2+a*x-1,x^4+D*x^2+D)^p==x^3-x^2+(a^2+2)*x-a^2-5
0
? kronecker(a,p)
-1
Yes, thanks for catching that. Indeed what I said was false. I meant Jacobi(D | p) = -1 not Jacobi(a | p) = -1..

Code:
(12:34) gp > kronecker(D,p)
%43 = 1
(12:34) gp >
For a = 5, I found those in the "plus" category are congruent p = {8, 10, 12, 15, 18, 26, 27} mod 29, and the "minus" category are congruent p = {2, 3, 11, 14, 17, 19, 21} mod 29.

a = 6 is quite interesting:
"plus": p = {7, 11, 19, 21, 29, 33, 57, 63} mod 80
"minus": p = {17, 23, 47, 51, 59, 61, 69, 73} mod 80

Still, no pattern, and why does it appear to be so random?

Last fiddled with by carpetpool on 2020-03-01 at 20:48
carpetpool is offline   Reply With Quote
Old 2020-03-03, 00:34   #4
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22·79 Posts
Smile

I was curious to find composites passing one of these two tests. To my suprise, not a single [p,a] pair with (p, |a|) < 100k!

Code:
(21:18) gp > for(p=1,100000, if(isprime(p)==0, for(a=1,p, D=a^2+4; if(kronecker(D,p)==(-1) & Mod(Mod(1,p)*x^2-a*x-1,x^4+D*x^2+D)^p==x^3-x^2+(a^2+2)*x-a^2-5, print([p,a])))))
(11:29) gp >
Code:
(21:18) gp > for(p=1,100000, if(isprime(p)==0, for(a=1,p, D=a^2+4; if(kronecker(D,p)==(-1) & Mod(Mod(1,p)*x^2+a*x-1,x^4+D*x^2+D)^p==x^3-x^2+(a^2+2)*x-a^2-5, print([p,a])))))
(11:24) gp >
carpetpool is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Patterns in primes that are primitive roots / Gaps in full-reptend primes mart_r Prime Gap Searches 14 2020-06-30 12:42
Goldbach's Conjecture: Hunting Counterexamples Christenson Math 19 2011-09-07 01:44
Can You See The Patterns..? wustvn Puzzles 7 2008-11-20 14:00
Counterexamples needed Unregistered Information & Answers 14 2007-05-30 08:29
Patterns SK8ER-91823 Twin Prime Search 4 2007-04-14 12:52

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

Sat Oct 31 01:51:08 UTC 2020 up 50 days, 23:02, 2 users, load averages: 1.84, 1.83, 1.75

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