Je montre ici qu'il est possible de trouver un résultat équivalent pour p=1 [mod 4], avec un nouveau test de primalité correspondant, une généralisation aux chaînes de Cunningham et des tests de primalité d'un nouveau type ("en grappe").
 

Théorème 1:

    Si p=1 [mod 4] est premier, q=2p+1 est aussi premier si et seulement si q divise 2^p + 1.

    C'est aussi un test de primalité pour les nombres de Sophie Germain avec p=4a+1.
    Il peut être utilisé avec les nombres de Proth p=k.2ⁿ+1.
 
 Démonstration :
    1) Si p=1 [mod 4] et q=2p+1 sont premiers alors q divise 2^p+1 :
        En effet 2^2p-1 = (2^p-1)*(2^p+1)  et 2^2p-1 = 0 [mod q]  Th. de Fermat pour q.
        Comme p=1 [mod 4] ,  q=3 [mod 8] , donc (2/q) = -1 , 2 <> m² [mod q]  ou 2^p<> m^2p [mod q].
        Or m^2p=1 [mod q] . Donc q ne divise pas 2^p-1, il divise 2^p+1.
    2) Si p premier et q=2p+1 divise 2^p+1 alors q est premier :
         En effet on utilise le test de primalité en n-1 : si pour chaque facteur premier f de n-1 il existe un entier a tel que a^n-1=1 [mod n] et a^(n-1)/f<>1 [mod n] alors n premier.
        On a ici n-1=2p , 2^2p= (2^p-1)*(2^p+1) +1, donc 2^2p= 1 [2p+1] puisque 2p+1 divise 2^p+1
 2²<>1 [2p+1] et 2^p=-1<> 1 [mod 2p+1 ] , donc q=2p+1 est premier.
 
 

---

 Généralisation aux chaînes de Cunningham de seconde espèce :

Théorème 2:

    Si p=3 [mod 4] et q=2p-1 sont  premiers alors q divise 2^p-1 + 1.
 
    C'est aussi un test de pseudo-primalité pour les  chaînes de Cunningham de seconde espèce avec p=4a+3 :
    Si p=3 [mod 4] premier et q=2p-1 divise 2^p-1 + 1,  q est premier probable.

    Démonstration :
        2^2p-2-1 = (2^p-1-1)*(2^p-1+1)  et 2^2p-2-1 = 0 [mod q]  Th. de Fermat pour q.
        Comme p=3 [mod 4] ,  q=5 [mod 8] , donc (2/q) = -1 , 2 <> m² [mod q]  ou 2^p-1<> m^2p-2 [mod q].
        Or m^2p-2=1 [mod q] . Donc q ne divise pas 2^p-1-1, il divise 2^p-1+1.
 

 Théorème 3:

    Si p=1 [mod 4] et q=2p-1 sont  premiers alors q divise 2^p-1 - 1.
 
    C'est aussi un test de pseudo-primalité pour les  chaînes de Cunningham de seconde espèce avec p=4a+1 :
    Si p=1 [mod 4] premier et q=2p-1 divise 2^p-1 - 1,  q est premier probable.

    Démonstration :
        2^2p-2-1 = (2^p-1-1)*(2^p-1+1)  et 2^2p-2-1 = 0 [mod q]  Th. de Fermat pour q.
        Comme p=1 [mod 4] ,  q=1 [mod 8] , donc (2/q) = 1 , 2 = m² [mod q]  ou 2^p-1= m^2p-2 [mod q].
        Or m^2p-2=1 [mod q] . Donc q divise 2^p-1-1.

 
    Mais comme p premier, p divise aussi 2^p-1-1.
 

Théorème 3a:

    Si p=1 [mod 4] et q=2p-1 sont  premiers alors p*q divise 2^p-1 - 1.
 
    C'est aussi un test de pseudo-primalité pour les  chaînes de Cunningham de seconde espèce avec p=4a+1 :
    Si n=1 [mod 4] et n₁=2n-1  et si n*n₁ divise 2^n-1 - 1,  alors n et n₁ sont premiers probables.

    La généralisation de ce test est même évidente et immédiate, puisque n=1 [mod 4], 2n-1=1[mod 4]  :
    Soit p_i, p_i+1, p_i+2 premiers tels que p_i=1[mod 4] , p_i+1=2p_i-1, p_i+2=2p_i+1-1.
    On a donc 2^(p_i+1-1)-1=0 [mod p_i+1*p_i+2], or 2^(p_i+1-1)-1=2^(2(p_i-1))-1 et 2^(p_i-1)-1=0[mod p_i], soit
         2^(p_i+1-1)-1=0 [mod p_i*p_i+1*p_i+2].
    Donc cette relation est nécessaire pour que p_i, p_i+1, p_i+2 soient premiers.

Pseudo test "en grappe" :

    Si n=1 [mod 4] et n₁=2n-1,  n₂=2n₁-1, ..., n_i=2n_i-1-1, et si n*n₁*n₂*..*n_i divise 2^(n_i-1-1) - 1,
        alors n,n₁,n₂, .., n_i  sont premiers probables, sinon un au moins des nombres n,n₁,n₂, .., n_i  est composé.
    Cette méthode qui permet un pseudo test de plusieurs nombres en même temps peut accélèrer considérablement la recherche des chaînes de Cunningham de seconde espèce de longueur quelconque. Elle est même bien adaptée pour tester les nombres de Proth n=k.2ⁿ+1 (forme 4a+1) "en grappe", un test complet de chaque nombre n'étant effectué que si ce premier test passe.

Des compléments à ces tests (prochainement ...)

• Le site des nombres premiers   de Chris Caldwell .
• Yves Gallot's Proth.exe and Cunningham Chains  de Warut Roonguthai.
• Psieve - Sieving exponents for k.2^n+-1  de Chris Nash.