## Re: now 5 selfridge test (puzzle)

Expand Messages
• ... Here are some near-refutations: 5444489 1349449 187741 5444489 2475895 187741 5444489 3039118 187741 5444489 3790082 187741 5444489 4165564 187741 5444489
Message 1 of 46 , Mar 9, 2012
• 0 Attachment
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>
>
>
> --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
> >
> > Hi,
> >
> > I have added a Fermat test to make a 1+1+1+2 selfridge test:
> >
> > For N>5, with gcd(6,N)==1, find an integer x:
> > gcd(x^3-x,N)==1
> > kronecker(x^2-4,N)==-1
> >
> > and check:
> > (x+2)^((N-1)/2)==kronecker(x+2,N) (mod N) (Euler)
> > (x-2)^((N-1)/2)==kronecker(x-2,N) (mod N) (Euler)
> > x^(N-1)==1 (mod N) (Fermat)
> > L^(N+1) == 1 (mod N, L^2-x*L+1) (Lucas)
> >
>
> Note: I should say gcd(30,N)==1 because gcd(x^3-x,N)==1 and kronecker(x^2-4,n)==-1.
>
>
> Now consider combining the 2 Euler tests with the Lucas test:
>
> (L*D)^((n+1)/2)==D (mod N, L^2-x*L+1) (D=x^2-4.)
>
> with the restriction kronecker(x+2,N)==-1.
>
> These together with the Fermat test makes for a 1+2-selfridge test.
>
> Can you find a counterexample?
>
> So far the near-refutation from Pinch's carmichael list is:
> N,x,gcd(x^2-1)
> ------------------
> 1909001 884658 1909001
>

Here are some near-refutations:
5444489 1349449 187741
5444489 2475895 187741
5444489 3039118 187741
5444489 3790082 187741
5444489 4165564 187741
5444489 4353305 5444489
5444489 4541046 187741

I am not sure about my claim: It could be 1+3-selfridge? If this is the case, it make more sense to do:
x^(N-1)==1 (mod N)
D^((N-1)/2)==-1 (mod N)
L^((N+1)/2)==-1 (mod N, L^2-x*L+1)
where kronecker(x+2,n)==-1
and kronecker(D,N)==-1
and gcd(x^3-x,N)==1

Paul
• ... Combining fails with the composite counterexample n=256999 and x=32768, However, I have tested the 1+1+1+2 conjecture up to n
Message 46 of 46 , Apr 14, 2012
• 0 Attachment
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>
>
>
> --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
> >
> > Hi,
> >
> > I have added a Fermat test to make a 1+1+1+2 selfridge test:
> >
> > For N>5, with gcd(6,N)==1, find an integer x:
> > gcd(x^3-x,N)==1
> > kronecker(x^2-4,N)==-1
> >
> > and check:
> > (x+2)^((N-1)/2)==kronecker(x+2,N) (mod N) (Euler)
> > (x-2)^((N-1)/2)==kronecker(x-2,N) (mod N) (Euler)
> > x^(N-1)==1 (mod N) (Fermat)
> > L^(N+1) == 1 (mod N, L^2-x*L+1) (Lucas)
> >
>
> Note: I should say gcd(30,N)==1 because gcd(x^3-x,N)==1 and kronecker(x^2-4,n)==-1.
>
>
> Now consider combining the 2 Euler tests with the Lucas test:
>
> (L*D)^((n+1)/2)==D (mod N, L^2-x*L+1) (D=x^2-4.)
>
> with the restriction kronecker(x+2,N)==-1.
>
> These together with the Fermat test makes for a 1+2-selfridge test.
>
> Can you find a counterexample?
>
> So far the near-refutation from Pinch's carmichael list is:
> N,x,gcd(x^2-1)
> ------------------
> 1909001 884658 1909001
>
> Paul
>

Combining fails with the composite counterexample n=256999 and x=32768, However, I have tested the 1+1+1+2 conjecture up to n<10^7,

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