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 aq tel que aqn–1 ≡ 1 (mod n) et pgcd(aq(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 rq l'exposant de chaque facteur premier q dans la décomposition de f.
Soient p un facteur premier de n et dq l'ordre multiplicatif de aq modulo p. Alors, dq divise n – 1 mais pas (n – 1)/q, donc (n – 1)/dq est un entier non divisible par q. Or n – 1 est divisible par qrq.
Par conséquent, qrq divise dq et (a fortiori) p – 1. Le produit f des qrq 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, , 3e éd. (lire en ligne), p. 52.
- ↑ (en) John Brillhart, D. H. Lehmer et J. L. Selfridge, « New primality criteria and factorizations of 2m ± 1 », Math. Comp., vol. 29, no 130, , p. 620-647 (lire en ligne), Th. 4.
Arithmétique et théorie des nombres
