Théorème de Pocklington

En arithmétique, le théorème de Pocklington[1]^,[2]^,[3] est la généralisation suivante du théorème de Proth et du test de primalité de Lucas-Lehmer :

Soient n, f et r trois entiers strictement positifs tels que :

n – 1 = f r ;

f et r sont premiers entre eux ;

pour tout facteur premier q de f, il existe un entier a_q tel que a_q^n–1 ≡ 1 (mod n) et pgcd(a_q^(n–1)/q – 1, n) = 1.
Alors, tout facteur premier de n est congru à 1 modulo f. En particulier : si f ≥ r alors n est premier.

Démonstration

Notons r_q l'exposant de chaque facteur premier q dans la décomposition de f.

Soient p un facteur premier de n et d_q l'ordre multiplicatif de a_q modulo p. Alors, d_q divise n – 1 mais pas (n – 1)/q, donc (n – 1)/d_q est un entier non divisible par q. Or n – 1 est divisible par q^r_q.

Par conséquent, q^r_q divise d_q et (a fortiori) p – 1. Le produit f des q^r_q divise donc aussi p – 1

Références

(en) H. C. Pocklington (de), « The determination of the prime or composite nature of large numbers by Fermat's theorem », Proc. Cambridge Philos. Soc., vol. 18,‎ 1914-1916, p. 29-30.
(en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, 3^e éd. (lire en ligne), p. 52.
(en) John Brillhart, D. H. Lehmer et J. L. Selfridge, « New primality criteria and factorizations of $2 m \pm 1$ », Math. Comp., vol. 29, n^o 130,‎ 1975, p. 620-647 (lire en ligne), Th. 4.

Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (en) H. C. Pocklington (de), « The determination of the prime or composite nature of large numbers by Fermat's theorem », Proc. Cambridge Philos. Soc., vol. 18,‎ 1914-1916, p. 29-30.

[2] (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, 3^e éd. (lire en ligne), p. 52.

[3] (en) John Brillhart, D. H. Lehmer et J. L. Selfridge, « New primality criteria and factorizations of $2 m \pm 1$ », Math. Comp., vol. 29, n^o 130,‎ 1975, p. 620-647 (lire en ligne), Th. 4.