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+1 prime for p=2) :
p=2,3,5,7,13,17,19,31,61,127.
Therefore for these values of p, gcd(2^2p-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 (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₀ a prime number > 254, if we find a_i such p₁=a_i*p₀+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₀+1)+1)+1) .... ,  and p_n can be represented in general manner by the certificate of primality : p₀->(a_i,a_j,a_k,...), constituted of n primes (even if p₀<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*2³⁰+1)->(4,26,254) = 3*2³⁰+1,4*(3*2³⁰+1)+1, ...........
                 (45*2¹¹⁹-1)->(62,122) =  45*2¹¹⁹-1,62*(45*2¹¹⁹-1)+1, ..........                 

With this test why not research prime records  P=a_i*(large prime p₀)+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₀ is increased.

Soon a program using this method ...