Je montre ici qu'il est possible de trouver un test de primalité aussi simple sans faire intervenir la forme de p.
 

Théorème :

    Si p >=5 est premier, q=2p+1 est aussi premier si et seulement si q divise 3^p-1.

  
 Démonstration :

    1) Si p et q=2p+1 sont premiers alors q divise 3^p-1 :
En effet 3^2p-1 = (3^p-1)*(3^p+1)  et 3^2p-1 = 0 [mod q]  Th. de Fermat pour q.
Si p>= 5, p=6*a-1 ou p=6*a+1.Si p=6*a+1, q=12*a+3 = 0 [mod 3], q non premier, donc p=6*a-1, et q=12*a-1.
Comme q =3 [mod 4] et 3 =3 [mod 4] , (3/q)=-(q/3)=-(-1/3)=1,donc (3/q) = 1 , donc q divise 3^p-1.

    2) Si p premier et q=2p+1 divise 3^p-1 alors q est premier :
On utilise le "Well Known theorem" ou n=hp^k+1 avec h=2, p premier n=q et k=1, il vient :
Si q=2p+1, p premier et p>2, s'il existe un entier a tel que a^q-1 = 1 [mod q] et pgcd(a²-1,q) =1 alors q premier.
Si a=3, 3^p = 1 [mod q] ou 3^2p=3^q-1 = 1 [mod q] est vérifié et pgcd(3²-1=8,q) =1, donc q=2p+1 est premier.
 

Des compléments et conséquences (prochainement ...)