**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 2 ^{n-1 }= 1 mod n** .

Demonstration :

We use the "Well Known theorem" where n=hq^{k}+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
a^{n-1} = 1 mod n and gcd(a^{2p}-1,n) =1 then n is prime.

If a=2 we have evidently in particular 2^{n-1} = 1 mod n (Fermat
theorem).

But 2^{2p}-1=(2^{p}+1)(2^{p}-1), and if p is a Mersenne
prime, Mp=2^{p}-1 prime,

and if 2^{p}+1=3*p1, with p1 prime, 2^{2p}-1=3*p1*Mp.

As n=2pq+1 < p1=(2^{p}+1)/3 and n<Mp, and if n<>0 mod
3 , gcd(2^{2p}-1,n)=1.

**In practice it exists only 10 known values with Mp and
p1=(2 ^{p}+1)/3 primes **(where 2

p=2,3,5,7,13,17,19,31,61,127.

Therefore for these values of p, gcd(2

Remarks : we can transform this test with a=3 or others bases, but common
values p where (a^{p}-1)/(a-1) and (a^{p}+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 p_{0 }a prime number > 254, if we find a_{i} such
p_{1}=a_{i}*p_{0}+1 prime, with a_{i}=
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 a_{i} :

p_{n} =
...(a_{k}(a_{j}*(a_{i}*p_{0}+1)+1)+1) ....
, and **p _{n} can be represented in general manner by the
certificate of primality :
p_{0}->(a_{i},a_{j},a_{k},...**),
constituted of n primes (even if p

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*2^{30}+1)->(4,26,254) =
3*2^{30}+1,4*(3*2^{30}+1)+1, ...........

(45*2^{119}-1)->(62,122) =
45*2^{119}-1,62*(45*2^{119}-1)+1, ..........

With this test why not research prime records P=a_{i}*(large
prime p_{0})+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 p_{0} is increased.

**Soon a program using this method ...**

Created by Henri Lifchitz : January, 24 1999.