Browse Groups

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

(14)
• NextPrevious
• ... 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
View Source
>
> 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 1 of 14 , Oct 8, 2012
View Source
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 1 of 14 , Oct 9, 2012
View Source
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 1 of 14 , Oct 9, 2012
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.