Accueil🇫🇷Chercher

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 :

Alors, tout facteur premier de n est congru à 1 modulo f. En particulier : si fr 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

  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, , 3e éd. (lire en ligne), p. 52.
  3. (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.
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.