Démonstration :

On utilise le "Well Known theorem" ou n=hq^k+1 avec h=2p, p et q premiers et k=1, il vient :
Si n=2pq+1, p et q premiers et q>2p, s'il existe un entier a tel que a^n-1 = 1 mod n et pgcd(a^2p-1,n) =1 alors n premier.

Si a=2 on a evidemment  en particulier 2^n-1 = 1 mod n (théorème de Fermat).
Or 2^2p-1=(2^p+1)(2^p-1), et si p est un premier de Mersenne, Mp=2^p-1 premier,
et si 2^p+1=3*p1, avec p1 premier, 2^2p-1=3*p1*Mp.
Comme n=2pq+1 < p1=(2^p+1)/3 et n<Mp et si  n<>0 mod 3 , pgcd(2^2p-1,n)=1.
En pratique il n'existe que 10 valeurs connus avec Mp et p1=(2^p+1)/3 premiers (ou 2^p+1 premier pour p=2),
soit p=2,3,5,7,13,17,19,31,61,127.
Donc pour ces valeurs de p, pgcd(2^2p-1,n)=1, et cette condition supprimée le test devient très simple.

Remarques : on peut transformer ce test avec a=3 ou d'autres bases, mais les valeurs p communes ou (a^p-1)/(a-1) et (a^p+1)/(a+1) sont premiers deviennent trop rares.

On en déduit aussi immédiatement , puisque que le test de Fermat est suffisant en base 2

Corollaire :

Les nombres de la forme n=a*p+1, avec n<>0 mod 3, p premier et a = 4,6,10,14,26,34,38,62,122 ou 254  ne sont jamais pseudo-premiers en base 2.

Utilisation itérative du test :

Soit p₀ un nombre premier > 254, si l'on trouve a_i tel que p₁=a_i*p₀+1 premier, avec a_i= 4,6,10,14,26,34,38,62,122 ou 254, il est possible de continuer le processus jusqu'a l'echec du test parmi les 10 valeurs de a.
De cette façon ,en utilisant un seul type de test, on construit un arbre de nombres premiers et des chaines liées par les a_i :

p_n = ...(a_k(a_j*(a_i*p₀+1)+1)+1) .... ,  et p_n peut être représenté de façon générale par le certificat de primalité : p₀->(a_i,a_j,a_k,...), constitué de n nombres premiers (même si p₀<254).

Exemples : 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, ..........                 

Avec ce test pourquoi ne pas rechercher des nombre premiers records  P=a_i*(grand nombre premier p₀)+1, si l'on dispose d'un programme optimisé ....et du temps de calcul nécessaire ? Cependant la probabilité de trouver un nombre premier par cette méthode n'est pas augmentée, et donc le processus aboutit plus souvent à l'échec quand p₀ augmente.

Prochaînement un programme utilisant cette méthode ...