Browse Groups

• ... I have coded it up in C. So far I have these where a gcd is needed, noting all N are 3 (mod 4): N,x,gcd ... 8911 3819 1273 19951 1124 281 77603 34975 1093
Feb 27, 2012 1 of 46
View Source
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>
>
>
>
> > > kronecker(x^2-4,N)==1
> > >
>
> I noticed I said "1" when of course I meant "-1".
>
> Let me restate the composite test:
>
> For N>5, with gcd(N,30)==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)
> > L^(N+1) == 1 (mod N, L^2-x*L+1)
> >
>
> I have checked Carmichael numbers < 10^7 and I am also checking non-Carmichael numbers. If things start to look good I will switch from pari-gp to The C Programming Language,
>

I have coded it up in C. So far I have these where a gcd is needed, noting all N are 3 (mod 4):

N,x,gcd
--------
8911 3819 1273
19951 1124 281
77603 34975 1093
77603 37161 1093
123251 56403 123251

and some from looking at Carmicahael numbers with a pari-gp script:
10267951 2239877 22177
10267951 5122887 22177

I feel I should explain briefly how I arrived at this conjecture...

For prime N:
(L+-1)^(N+1)==2+-x (mod N, L^2-x*L+1)

but (L+-1)^2==L^2+-2*L+1==(x+-2)*L (mod N, L^2-x*L+1)

so (x+-2)^((N+1)/2)*L((N+1)/2)==2+-x== +-(x+-2) (mod N, L^2-x*L+1)

or (x+-2)^((N-1)/2)*L((N+1)/2)==+-1 (mod N, L^2-x*L+1)

Then the test follows using the weaker L^(N+1)==1 (mod L^2-x*L+1)

Paul -- error prone
• ... Combining fails with the composite counterexample n=256999 and x=32768, However, I have tested the 1+1+1+2 conjecture up to n
Apr 14, 2012 46 of 46
View Source
--- 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.
• 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.