mersenneforum.org Patterns in primes (no counterexamples)
 Register FAQ Search Today's Posts Mark Forums Read

 2020-03-01, 17:52 #1 carpetpool     "Sam" Nov 2016 2×3×53 Posts 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).
2020-03-01, 18:26   #2
paulunderwood

Sep 2002
Database er0rr

DB016 Posts

Quote:
 Originally Posted by carpetpool 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

2020-03-01, 20:43   #3
carpetpool

"Sam"
Nov 2016

2·3·53 Posts

Quote:
 Originally Posted by paulunderwood 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

 2020-03-03, 00:34 #4 carpetpool     "Sam" Nov 2016 2·3·53 Posts 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 >

 Similar Threads Thread Thread Starter Forum Replies Last Post mart_r Prime Gap Searches 14 2020-06-30 12:42 Christenson Math 19 2011-09-07 01:44 wustvn Puzzles 7 2008-11-20 14:00 Unregistered Information & Answers 14 2007-05-30 08:29 SK8ER-91823 Twin Prime Search 4 2007-04-14 12:52

All times are UTC. The time now is 17:48.

Sun Nov 29 17:48:59 UTC 2020 up 80 days, 14:59, 4 users, load averages: 1.79, 1.93, 1.86