## 1+1+2 selfridge composite test question

Expand Messages
• Hi, let X=x+2 and Y=x-2 for an integer x: Let M=[X,-1;1,2] N=[Y,-1;1,-2] Form a new matrix: A=M^2-x*M+1 Then A=2*[X,-2;2,-Y]==[2*x+4,-4;4,-2*x+4] This has the
Message 1 of 14 , Sep 29, 2012
• 0 Attachment
Hi,

let X=x+2 and Y=x-2 for an integer x:

Let
M=[X,-1;1,2]
N=[Y,-1;1,-2]

Form a new matrix:
A=M^2-x*M+1

Then A=2*[X,-2;2,-Y]==[2*x+4,-4;4,-2*x+4]

This has the characteristic equation:
L^2-8*L-4*(x^2-8)==0

Let
P=8
Q=-4*(x^2-8)
R=Q/4

Let v=P^2/Q-2==16/(-x^2+8)-2 (if gcd(Q,n)==1)

Now form the 1+1+2 selfridge composite test for odd n with kronecker(D,n)==-1 where D=x^2-4:
gcd(x,n)==1
D^((n-1)/2)==-1 (mod n)
R^((n-1)/2)==kronecker(R,n) (mod n)
L^(n+1)==1 (mod n, L^2-v*L+1)

Is a 2-prp test implied by this?

Should I make the test on R "strong" with a negative kronecker symbol?

Paul
• ... I found a counterexample: n=5173601 (2-psp) and x=1630018. After a wriggle, the test becomes: kronecker(D,n)==-1 gcd(x,n)==1 X^((n-1)/2)==kronecker(X,n)
Message 2 of 14 , Sep 29, 2012
• 0 Attachment
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>
> Hi,
>
> let X=x+2 and Y=x-2 for an integer x:
>
> Let
> M=[X,-1;1,2]
> N=[Y,-1;1,-2]
>
> Form a new matrix:
> A=M^2-x*M+1
>
> Then A=2*[X,-2;2,-Y]==[2*x+4,-4;4,-2*x+4]
>
> This has the characteristic equation:
> L^2-8*L-4*(x^2-8)==0
>
> Let
> P=8
> Q=-4*(x^2-8)
> R=Q/4
>
> Let v=P^2/Q-2==16/(-x^2+8)-2 (if gcd(Q,n)==1)
>
> Now form the 1+1+2 selfridge composite test for odd n with kronecker(D,n)==-1 where D=x^2-4:
> gcd(x,n)==1
> D^((n-1)/2)==-1 (mod n)
> R^((n-1)/2)==kronecker(R,n) (mod n)
> L^(n+1)==1 (mod n, L^2-v*L+1)
>
> Is a 2-prp test implied by this?
>
> Should I make the test on R "strong" with a negative kronecker symbol?
>

I found a counterexample: n=5173601 (2-psp) and x=1630018.

After a wriggle, the test becomes:
kronecker(D,n)==-1
gcd(x,n)==1
X^((n-1)/2)==kronecker(X,n)
Y^((n-1)/2)==kronecker(Y,n)
R^(n-1)==kronecker(R,n) (mod n)
L^(n+1)==1 (mod n, L^2-v*L+1)

This is 1+1+1+2 selfridges :-(

My question remains: Is a 2-prp test implied by this?

Paul
• ... I meant: R^(n-1)==1 (mod n)
Message 3 of 14 , Sep 29, 2012
• 0 Attachment
> R^(n-1)==kronecker(R,n) (mod n)

I meant:
R^(n-1)==1 (mod n)
• ... To err is human; to recant, divine. David
Message 4 of 14 , Sep 29, 2012
• 0 Attachment
"paulunderwooduk" <paulunderwood@...> wrote:

> I found a counterexample...
> After a wriggle, the test becomes...

To err is human; to recant, divine.

David
• ... The gremlins win against the modified test; (psp-2) n=16070429 and x=6924798 is a counterexample. nuf said, Paul
Message 5 of 14 , Sep 30, 2012
• 0 Attachment
>
>
>
> "paulunderwooduk" <paulunderwood@> wrote:
>
> > I found a counterexample...
> > After a wriggle, the test becomes...
>
> To err is human; to recant, divine.
>

The gremlins win against the modified test; (psp-2) n=16070429 and x=6924798 is a counterexample.

nuf said,

Paul
• ... ? n=16070429;x=6924798;R=-x^2+8;Mod(R,n)^((n-1)/2) Mod(12860271, 16070429) which is neither +-1. Maybe I should adhere to C&P 3.6.3. In the meantime I will
Message 6 of 14 , Sep 30, 2012
• 0 Attachment
>
> (psp-2) n=16070429 and x=6924798 is a counterexample.
>

? n=16070429;x=6924798;R=-x^2+8;Mod(R,n)^((n-1)/2)
Mod(12860271, 16070429)

which is neither +-1.

Maybe I should adhere to C&P 3.6.3.

In the meantime I will carry on testing odd psp-2s to 2^32 -- this might help countering another test I have which has been tested for all odd n< 2.5*10^7

Paul
• Hi again, [x+2,-2;2,x-2] has the characteristic equation L^2-8*L-4*(x^2-8)==0 Let P=8 Q=-4*(x^2-8) Then v=P^2/Q-2 == -2*x^2/(x^2-8) For this new test of odd n,
Message 7 of 14 , Sep 30, 2012
• 0 Attachment
Hi again,

[x+2,-2;2,x-2] has the characteristic equation
L^2-8*L-4*(x^2-8)==0

Let
P=8
Q=-4*(x^2-8)

Then
v=P^2/Q-2 == -2*x^2/(x^2-8)

For this new test of odd n, find x such that:
gcd(x,n)==1
gcd(x^2-8,n)==1
kronecker(x^2-4)==-1

and perform the sub-tests:
(x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
(x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
x^(n-1)==1 (mod n)
L^(n+1)==1 (mod n, L^2-v*L+1)

I am testing all x against psp-2 n below 2^32.

Do I need to test non-psp-2s?

Paul
• ... The matrix should be [2*x+4,-4;4,-2*x+4] Paul
Message 8 of 14 , Sep 30, 2012
• 0 Attachment
> [x+2,-2;2,x-2] has the characteristic equation
> L^2-8*L-4*(x^2-8)==0

The matrix should be [2*x+4,-4;4,-2*x+4]

Paul
• ... It make no difference to the test if [x+2,-2;2,-x+2] is used , with its characteristic equation L^2-4*L-(x^2-8)==0, Paul
Message 9 of 14 , Sep 30, 2012
• 0 Attachment
>
> > [x+2,-2;2,x-2] has the characteristic equation
> > L^2-8*L-4*(x^2-8)==0
>
> The matrix should be [2*x+4,-4;4,-2*x+4]
>

It make no difference to the test if [x+2,-2;2,-x+2] is "used", with its characteristic equation L^2-4*L-(x^2-8)==0,

Paul
• The characteristic equation of [x+2,-2;2,-x+2] is L^2-4*L-x^2+8==0 Let P=4 Q=-(x^2-8) ... The gremlins score another goal with their counterexample:
Message 10 of 14 , Oct 4, 2012
• 0 Attachment
The characteristic equation of [x+2,-2;2,-x+2]
is L^2-4*L-x^2+8==0

Let
P=4
Q=-(x^2-8)

> Then
> v=P^2/Q-2 == -2*x^2/(x^2-8)
>
> For this new test of odd n, find x such that:
> gcd(x,n)==1
> gcd(x^2-8,n)==1
> kronecker(x^2-4)==-1
>
> and perform the sub-tests:
> (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
> (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
> x^(n-1)==1 (mod n)
> L^(n+1)==1 (mod n, L^2-v*L+1)
>
> I am testing all x against psp-2 n below 2^32.
>

The gremlins score another goal with their counterexample:
n==741470549 and x==68216238.

I refuse to take their bait of x^((n-1)/2)!=+-1 (mod n) and "recant"

Paul
• ... I noticed: x^((n-1)/2)==593203119 (mod n) L^((n+1)/2)==593203119 (mod n) This got me thinking again... kronecker(v^2-4,n)
Message 11 of 14 , Oct 4, 2012
• 0 Attachment
>
> The characteristic equation of [x+2,-2;2,-x+2]
> is L^2-4*L-x^2+8==0
>
> Let
> P=4
> Q=-(x^2-8)
>
> > Then
> > v=P^2/Q-2 == -2*x^2/(x^2-8)
> >
> > For this new test of odd n, find x such that:
> > gcd(x,n)==1
> > gcd(x^2-8,n)==1
> > kronecker(x^2-4)==-1
> >
> > and perform the sub-tests:
> > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
> > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
> > x^(n-1)==1 (mod n)
> > L^(n+1)==1 (mod n, L^2-v*L+1)
> >
> > I am testing all x against psp-2 n below 2^32.
> >
>
> The gremlins score another goal with their counterexample:
> n==741470549 and x==68216238.
>

I noticed:
x^((n-1)/2)==593203119 (mod n)
L^((n+1)/2)==593203119 (mod n)

This got me thinking again...

kronecker(v^2-4,n)
==kronecker((4*x^4-4*(-x^2+8)^2)/(-x^2+8)^2,n)
==kronecker(4*x^4-4*(x^4-16*(x^2-4)),n)
==kronecker(x^2-4,n)
==-1

Hence L^((n+1)/2)==kronecker(v+2,n) (mod n, L^2-v*L+1)

kronecker(v+2,n)
==kronecker(P^2/Q,n)
==kronecker(Q,n)

Thus the Lucas test now becomes
L^((n+1)/2)==kronecker(-x^2+8,n)

I will continue testing psp-2s :-)

Paul
• Hi, for odd n with minimal x such that kronecker(x^2-4,n)==-1, if x=0 then 2 selfridge: (L+2)^(n+1)==5 (mod n, L^2+1) if x=1 then 3 selfridge: gcd(7,n)==1
Message 12 of 14 , Oct 8, 2012
• 0 Attachment
Hi,

for odd n with minimal x such that kronecker(x^2-4,n)==-1,

if x=0 then 2 selfridge:
(L+2)^(n+1)==5 (mod n, L^2+1)

if x=1 then 3 selfridge:
gcd(7,n)==1
3^((n-1)/2)==kronecker(3,n) (mod n)
L^((n+1)/2)==kronecker(3,n) (mod n, L^2-(2/7)*L+1)

if x=3 then 4 selfridge:
gcd(3,n)==1
3^(n-1)==1 (mod n)
5^((n-1)/2)==-1 (mod n)
L^((n+1)/2)==kronecker(-1,n) (mod n, L^2+18*L+1)

if n>x>3 then 4 selfridge:
(L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1)
(L-2)^(n+1)==5-2*x (mod n, L^2-x*L+1)

This program is on average (1/2)*2+(1/2)*((1/2)*3+(1/2)*((1/2)*4+(1/2)*4)==2.75 selfridges.

It is a mix of "section 10" of my paper in the file section of this group:

Paul
• ... This should be L^((n+1)/2)==kronecker(7,n) (mod n, L^2-(2/7)*L+1)
Message 13 of 14 , Oct 9, 2012
• 0 Attachment
I need to report an of error:

> for odd n with minimal x such that kronecker(x^2-4,n)==-1,
>
> if x=0 then 2 selfridge:
> (L+2)^(n+1)==5 (mod n, L^2+1)
>
> if x=1 then 3 selfridge:
> gcd(7,n)==1
> 3^((n-1)/2)==kronecker(3,n) (mod n)
> L^((n+1)/2)==kronecker(3,n) (mod n, L^2-(2/7)*L+1)

This should be L^((n+1)/2)==kronecker(7,n) (mod n, L^2-(2/7)*L+1)

>
> if x=3 then 4 selfridge:
> gcd(3,n)==1
> 3^(n-1)==1 (mod n)
> 5^((n-1)/2)==-1 (mod n)
> L^((n+1)/2)==kronecker(-1,n) (mod n, L^2+18*L+1)
>
> if n>x>3 then 4 selfridge:
> (L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1)
> (L-2)^(n+1)==5-2*x (mod n, L^2-x*L+1)
>
> This program is on average (1/2)*2+(1/2)*((1/2)*3+(1/2)*((1/2)*4+(1/2)*4)==2.75 selfridges.
>
> It is a mix of "section 10" of my paper in the file section of this group:
>
> Paul
>
• I have changed the rules and added a puzzle. For odd n with x chosen in order from {0,1,6,3,all others} so that kronecker(x^2-4,n)==-1, ... if x=6 then 4
Message 14 of 14 , Oct 9, 2012
• 0 Attachment
I have changed the rules and added a puzzle.

For odd n with x chosen in order from {0,1,6,3,all others} so that kronecker(x^2-4,n)==-1,

> > if x=0 then 2 selfridge:
> > (L+2)^(n+1)==5 (mod n, L^2+1)
> >
> > if x=1 then 3 selfridge:
> > gcd(7,n)==1
> > 3^((n-1)/2)==kronecker(3,n) (mod n)
> L^((n+1)/2)==kronecker(7,n) (mod n, L^2-(2/7)*L+1)

if x=6 then 4 selfridge:
gcd(21,n)==1
6^(n-1)==1 (mod n) (*)
2^((n-1)/2)==kronecker(2,n) (mod n)
L^((n+1)/2)==kronecker(-7,n) (mod n, L^2+(18/7)*L+1)

> >
> > if x=3 then 4 selfridge:
> > gcd(3,n)==1
> > 3^(n-1)==1 (mod n)
> > 5^((n-1)/2)==-1 (mod n)
> > L^((n+1)/2)==kronecker(-1,n) (mod n, L^2+18*L+1)
> >
> > if n>x>3 then 4 selfridge:
> > (L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1)
> > (L-2)^(n+1)==5-2*x (mod n, L^2-x*L+1)
> >
> > This program is on average (1/2)*2+(1/2)*((1/2)*3+(1/2)*((1/2)*4+(1/2)*4)==2.75 selfridges.
> >

Puzzle: find a counterexample for x==6 where (*) is dropped,

Paul
Your message has been successfully submitted and would be delivered to recipients shortly.