Re: 1+1+1+2 selfridge composite test and a question

Expand Messages
• ... 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 1 of 14 , Oct 4, 2012
>
> 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 2 of 14 , Oct 8, 2012
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 3 of 14 , Oct 9, 2012
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 4 of 14 , Oct 9, 2012
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.