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

[modifier | modifier le code]

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

[modifier | modifier le code]

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, 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, 1975, p. 620-647 (lire en ligne), Th. 4.

v · m

Nombres premiers

Donnés par une formule |  | combinatoire |

* factoriel (n!±1)
* primoriel (pn#±1)
* Euclide (pn#+1)

|

polynomiale |

* Pythagore (4n \+ 1)
* cubain (x3 − y3)/(x − y)
* quatrain (x4 \+ y4)

exponentielle |

* Fermat (22n \+ 1)
* Mersenne (2p – 1)
* Double de Mersenne (22p–1 –1)
* Pierpont (2u3v \+ 1)
* Carol ((2n – 1)2 – 2)
* Kynea ((2n \+ 1)2 – 2)
* Thebit (3·2n – 1)
* Wagstaff ((2p \+ 1)/3)
* Proth (k2n \+ 1)
* Cullen (n2n \+ 1)
* Woodall (n2n – 1)
* Mills (⌊A3n⌋)

Appartenant à une suite |

* Fibonacci
* Lucas
* Motzkin
* Bell
* Pell
* Perrin
* Newman-Shanks-Williams

Ayant une propriété remarquable |

* bon
* chanceux
* fortuné
* Higgs
* illégal
* Pillai
* Ramanujan
* régulier
* Stern
* super
* supersingulier
* Wall-Sun-Sun
* Wieferich
* Paire de Wieferich
* Wilson
* Wolstenholme

Ayant une propriété dépendant de la base |

* diédral
* palindrome
* Reimerp
* répunit (10n − 1)/9
* permutable
* circulaire
* délicat
* tronquable
* minimal
* long
* unique
* Smarandache-Wellin
* partie entière de puissances de constante
* troncature de constante

Propriétés mettant en jeu plusieurs nombres |  | singleton |

* Chen {p ; p+2 premier ou semi-premier}
* équilibré (faible, fort) {pn ; pn = (<, >) (pn–1 \+ pn+1)/2}
* Sophie Germain {p ; 2p \+ 1 premier}
* sûr {p ; (p – 1)/2 premier}

|

n-uplet |

* jumeaux (p, p \+ 2)
* cousins (p, p \+ 4)
* sexy (p, p \+ 6)
* triplet (p, p \+ 2 ou p \+ 4, p \+ 6)
* quadruplet (p, p \+ 2, p \+ 6, p \+ 8)
* quintuplet (p – 4, p, p \+ 2, p \+ 6, p \+ 8) ou (p, p \+ 2, p \+ 6, p \+ 8, p \+ 12)
* sextuplet (p – 4, p, p \+ 2, p \+ 6, p \+ 8, p \+ 12)

suite |

* progression arithmétique (p + an)
* chaîne de Cunningham (p, 2p ± 1, etc.)

Classement par taille |

* titanesque (1 000+ chiffres)
* gigantesque (10 000+)
* méga (1 000 000+)
* record

Généralisations (entier quadratique) |

* Eisenstein
* Gauss

Nombre composé |

* pseudo-premier
* presque premier
* semi-premier
* interpremier

Nombre connexe |

* probable (NPP)

Test de primalité |

* Crible d'Ératosthène
* Test de Fermat
* Test de Lucas-Lehmer
* Test de Lucas-Lehmer pour les nombres de Mersenne
* Test de Pépin
* Test de Miller-Rabbin
* Test de Solovay-Strassen
* Test AKS

Conjectures et théorèmes de théorie des nombres |

* Conjecture d'Agoh-Giuga
* Conjecture d'Artin
* Conjecture de Bateman-Horn
* Conjecture de Bouniakovski
* Conjecture de Brocard
* Conjecture de Cramér
* Conjecture de Dickson
* Conjecture d'Elliott-Halberstam
* Conjecture de Firoozbakht
* Conjecture de Goldbach
* forte
* faible
* Conjecture de Grimm
* Conjecture de Hardy-Littlewood
* première
* seconde
* Conjecture de Legendre
* Conjecture de Lemoine
* Conjecture des nombres premiers de Waring
* Conjecture d'Oppermann
* Conjecture de Polignac
* Conjecture de Redmond-Sun
* Fonction de compte des nombres premiers
* Formules pour les nombres premiers
* Hypothèse H de Schinzel
* Nouvelle conjecture de Mersenne
* Théorème de Green-Tao
* Théorème des nombres premiers
* Théorème de la progression arithmétique
* Théorème de Rosser
* Théorème de Vinogradov

Constantes liées aux nombres premiers |

* Constante de Brun
* Constante de Legendre
* Constante de Mills
* Constante des nombres premiers
* Constante de Copeland-Erdős

* Prime Pages
* Liste de nombres premiers
* Liste de suites de nombres premiers

* Arithmétique et théorie des nombres

*[(en)]: Langue : anglais
*[vol.]: volume
*[p.]: pages
*[3e]: troisième
*[éd.]: édition
*[no]: numéro
*[v]: Voir ce modèle.
*[m]: Modifier ce modèle. Merci de prévisualiser avant de sauvegarder.