mersenneforum.org Patterns in primes (no counterexamples)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2020-03-01, 17:52 #1 carpetpool     "Sam" Nov 2016 3·103 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

26×53 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

3·103 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 3·103 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 >

 Thread Tools

 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 13:33.

Fri Sep 18 13:33:06 UTC 2020 up 8 days, 10:44, 1 user, load averages: 1.64, 1.84, 1.80

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.