I show here that it is possible to find a same result
for p=1 [mod 4], with a new corresponding primality test, a generalization
to Cunningham chains of second kind and primality tests of a new type ("in
cluster").
It is also a primality test for Sophie Germain primes
with p=4a+1.
It can be used with Proth numbers
p=k.2n+1.
Demonstration :
1) If p=1 [mod 4] and q=2p+1 are prime then q divides
2p+1 :
Indeed 22p-1 =
(2p-1)*(2p+1) and 22p-1 = 0 [mod q]
(Fermat th. for q).
As p=1 [mod 4] , q=3 [mod
8] , therefore (2/q) = -1 , 2 <> m2 [mod q] or
2p<> m2p [mod q].
But m2p=1 [mod q] .
Therefore q does not divide 2p-1, it divides 2p+1.
2) If p is prime and q=2p+1 divides 2p+1 then
q is prime :
Indeed we use the primality
test in n-1 : if for each prime factor f of n-1 there exists an integer
a such that
an-1=1 [mod n] and a(n-1)/f<>1 [mod n]
then n is prime.
We have here n-1=2p ,
22p= (2p-1)*(2p+1) +1, therefore
22p= 1 [2p+1] since 2p+1 divides 2p+1
22<>1 [2p+1] and 2p=-1<> 1 [mod 2p+1
] , therefore q=2p+1 is prime.
If p=3 [mod 4] and q=2p-1 are prime then q divides
2p-1 + 1.
It is also a pseudo-primality test for Cunningham chains
of second kind with p=4a+3 :
If p=3 [mod 4] is prime and q=2p-1 divides 2p-1
+ 1, q is probably prime.
Demonstration :
22p-2-1 =
(2p-1-1)*(2p-1+1) and 22p-2-1 = 0
[mod q] (Fermat th. for q).
As p=3 [mod 4] , q=5 [mod
8] , therefore (2/q) = -1 , 2 <> m2 [mod q] or
2p-1<> m2p-2 [mod q].
But m2p-2=1 [mod q]
. Therefore q does not divide 2p-1-1, it divides
2p-1+1.
If p=1 [mod 4] and q=2p-1 are prime
then q divides 2p-1 - 1.
It is also a pseudo-primality test for Cunningham chains
of second kind with p=4a+1 :
If p=1 [mod 4] is prime and q=2p-1 divides
2p-1 - 1, q is probably prime.
Demonstration :
22p-2-1 =
(2p-1-1)*(2p-1+1) and 22p-2-1 = 0
[mod q] (Fermat th. for q).
As p=1 [mod 4] , q=1 [mod
8] , therefore (2/q) = 1 , 2 = m2 [mod q] or
2p-1= m2p-2 [mod q].
But m2p-2=1 [mod q]
. Therefore q divides 2p-1-1.
But as p is prime, p divides also 2p-1-1.
If p=1 [mod 4] and q=2p-1 are prime
then p*q divides 2p-1 - 1.
It is also a pseudo-primality test for Cunningham chains
of second kind with p=4a+1 :
If n=1 [mod 4] and n1=2n-1 and if
n*n1 divides 2n-1 - 1, then n and n1
are probably prime.
The generalization of this test is even evident and immediate,
since n=1 [mod 4], 2n-1=1[mod 4] :
Let pi, pi+1, pi+2 prime
such that pi=1[mod 4] , pi+1=2pi-1,
pi+2=2pi+1-1.
Therefore we have 2^(pi+1-1)-1=0 [mod
pi+1*pi+2], but
2^(pi+1-1)-1=2^(2(pi-1))-1 and
2^(pi-1)-1=0[mod pi],
2^(pi+1-1)-1=0
[mod pi*pi+1*pi+2].
Therefore this relationship is necessary in order that
pi, pi+1, pi+2 are prime.
Pseudo test "in cluster" :
If n=1 [mod 4] and n1=2n-1,
n2=2n1-1, ..., ni=2ni-1-1, and
if n*n1*n2*..*ni divides
2^(ni-1-1) - 1,
then
n,n1,n2, .., ni are probably prime,
otherwise one at least of numbers n,n1,n2, .., ni
is composite.
This method that allows a pseudo test
of several numbers at the same time can speed up considerably
the research of Cunningham chains of second kind with any length. It
is even well adapted to test numbers Proth n=k.2n+1 (form 4a+1)
"in cluster", a complete test of each number being undertaken only if this
first test passes.
p prime | 2p+1 prime ? | 2p-1 prime ? |
p=1 [mod 4] | New test 2p+1 = 0 [mod 2p+1] |
New probable test 2p-1-1 = 0 [mod 2p-1] |
p=3 [mod 4] | Euler-Lagrange test 2p-1 = 0 [mod 2p+1] |
New probable test 2p-1+1 = 0 [mod 2p-1] |
n=1 [mod 4] n1=2n-1, n2=2n1-1, ..., ni=2ni-1-1 |
New probable test "in cluster" 2^(ni-1-1) - 1 = 0 [mod n*n1*n2*..*ni] |
Complements to these tests (soon ...)