## A simpler primality test for numbers n=a*p+1

Theorem :

If a = 4,6,10,14,26,34,38,62,122 or 254  and p prime > a,
n=a*p+1 is prime  if n<>0 mod 3  and if  2n-1 = 1 mod n
.

Demonstration :

We use the "Well Known theorem" where n=hqk+1 with h=2p, p and q are prime and k=1, it comes :
If n=2pq+1, p and q primes and q>2p, if there is an integer a such an-1 = 1 mod n and gcd(a2p-1,n) =1 then n is prime.

If a=2 we have evidently  in particular 2n-1 = 1 mod n (Fermat theorem).
But 22p-1=(2p+1)(2p-1), and if p is a Mersenne prime, Mp=2p-1 prime,
and if 2p+1=3*p1, with p1 prime, 22p-1=3*p1*Mp.
As n=2pq+1 < p1=(2p+1)/3 and n<Mp, and if n<>0 mod 3 , gcd(22p-1,n)=1.
In practice it exists only 10 known values with Mp and p1=(2p+1)/3 primes  (where 2p+1 prime for p=2) :
p=2,3,5,7,13,17,19,31,61,127.
Therefore for these values of p, gcd(22p-1,n)=1, and this condition suppressed the test becomes very simple.

Remarks : we can transform this test with a=3 or others bases, but common values p where (ap-1)/(a-1) and (ap+1)/(a+1) are primes become too rare.

We immediately deduce of the above demonstration, because the Fermat test is sufficient in base 2 :

Corollary :

Numbers of the form n=a*p+1, with n<>0 mod 3, p prime and a = 4,6,10,14,26,34,38,62,122 or 254  are never pseudo-primes in base 2.

Iterative utilization of the test :

Let p0 a prime number > 254, if we find ai such p1=ai*p0+1 prime, with ai= 4,6,10,14,26,34,38,62,122 or 254, it is possible to continue the process until the failure of the test among the 10 values of a.
With this manner, by using an unique type of test, we build a tree of prime numbers and chains linked together by the ai :

pn = ...(ak(aj*(ai*p0+1)+1)+1) .... ,  and pn can be represented in general manner by the certificate of primality : p0->(ai,aj,ak,...), constituted of n primes (even if p0<254).

Examples : 3->(4,4,14,26,122,38,26) = 3,13,53,743,19319,2356919,89562923,2328635999
5->(6,10,6,10,26,6,34,6) = 5,31,311,1867,18671,485447,2912683,99031223, 594187339
(3*230+1)->(4,26,254) = 3*230+1,4*(3*230+1)+1, ...........
(45*2119-1)->(62,122) =  45*2119-1,62*(45*2119-1)+1, ..........

With this test why not research prime records  P=ai*(large prime p0)+1, if we have an optimized program ....and the necessary computation time !? However the probability to find a prime by this method is not increased, and therefore the process ends more often to the failure when p0 is increased.

Soon a program using this method ...

Created by  Henri Lifchitz : January, 24 1999.