121 – Nombres premiers. Applications.

Références : Gourdon Algèbre, Perrin, Rombaldi, X-ENS Algèbre 1 Théorème 10. Expression des pgcd (et ppcm) avec les valuations p-adiques.
Corollaire 11. a ∨ b a ∧ b = |ab|
Proposition 12. — Si p premier ne divise pas a, alors p et a sont premiers entre
1 Arithmétique dans Z eux.
— Si p divise une produit a1 a2 , ...an , alors il divise au moins l’un des ai .
1.1 Division et nombres premiers entre eux
Théorème 13. Il y a une infinité de nombres premiers.
Définition 1. Soient a et b deux entiers relatifs. On dit que a divise b si il existe k Théorème 14. Répartition des nombres premiers (admis) : Le nombre d’entiers
n
∈ Z tel que b=ak. premiers inférieur ou égal à n est équivalent, quand n tend vers ∞, à ln(n)
Définition 2. Soient (a1 , a2 , ..., an ) des entiers. Comme nZ est un idéal de l’anneau
principal (Z, +), on peut définir le pgcd et le ppcm de la manière suivante :
— Il existe un unique entier d=pgcd(a1 , a2 , ..., an ) tel que a1 Z + a2 Z + ... + an Z = 2 Lien avec les structures algébriques clas-
dZ. d est aussi le plus grand entier qui divise tout les ai .
T T T
— Il existe un unique entier m=ppcm(a1 , a2 , ..., an ) tel que a1 Z a2 Z ... an Z =
siques
mZ. m est aussi le plus petit entier non-nul qui est multiple de tout les ai .
Si pgcd(a1 , a2 , ..., an )=1, on dit que (a1 , a2 , ..., an ) sont premiers entre-eux. 2.1 Lien avec la théorie des groupes
Théorème 3 (Théorème de Bézout). Soient (a1 , a2 , ..., an ) des nombres premiers Proposition 15. Si G est cyclique d’ordre n, tel que G =< g >, alors ses
entre eux. Alors il existe des entiers (u1 , ..., un ) tel que 1 = u1 a1 + ... + un an générateurs sont les g k avec k premier avec n.
Théorème 4 (Lemme de Gauss). Si c divise ab et si a et b sont premiers entre Corollaire 16. Un groupe de cardinal p premier est cyclique, engendré par n’importe
eux, alors c divise b. lequel de ses éléments.
Application 5. Si p est premier, alors pour tout j compris entre 1 et p-1, p divise Définition 17. Définition d’un p-groupe et des p-sylows.
j


.
p Application 18. Soit G un p-groupe (p premier plus grand que 2) qui opère sur
Proposition 6. Si a est premier avec (a1 , a2 , ..., an ), alors a est premier avec le un ensemble finie X. alors en notant X G = {x ∈ X | G.x = {x}}, on a
produit (a1 a2 ...an ) #(X G ) ≡ #(X) [mod p]

Proposition 7. Soient (a1 , a2 , ..., an ) premiers entre eux deux à deux et b un entier. Application 19. Pour tout nombre premier p, le centre d’un p-groupe n’est pas
Le produit a1 a2 , ...an divise b ssi ai divise b pour tout i. réduit à 1.
Théorème 20 (théorèmes de Sylow). Soit G un groupe d’ordre n = pa m avec p
qui ne divise pas m. Alors :
1.2 Nombres premiers et premières applications — il existe un sous-groupe de G d’ordre pa
— Les p-Sylows de G sont tous conjugués
Définition 8. Un entier naturel p plus grand que 2 est dit premier si ses seuls
diviseurs sont lui-même, 1 (et leurs opposés). Exemple : 3,5,7,13 — On note Np le nombre de p-Sylows, il vérifie Np |m et Np ≡ 1 (mod p)
Application 21. Soit G un groupe fini d’ordre n = pa m avec p qui ne divise pas
Théorème 9. Comme Z est un anneau factoriel, tout entier n> 1 dans Z s’écrit
αk m. Si G possède un unique p-sylow, alors celui-ci est distingué dans G
n = ±pα 1 α2
1 p2 ...pk avec (p1 , p2 , ..., pk ) des nombres premiers, (α1 , α2 , ..., αk ) des en-
tiers naturels non-nuls (αi est appelé valuation pi adique dans n.) Application 22. Un groupe d’ordre 63 n’est pas simple.
 Z
2.2 Anneaux nZ
et conséquences arithmétiques Z ×
Proposition 37. Si p est premier plus grand que 2. Le groupe ( pZ ) est
cyclique d’ordre p-1.
Proposition 23. Soit G un groupe cyclique d’ordre n, alors il est isomorphe à
Z
( nZ ,+) Théorème 38. Si p est premier plus grand que 2 et α > 2, alors le groupe
( pαZZ )× est cyclique d’ordre pα−1 (p − 1)
Définition 24. Soit A un anneau, l’application

φ: Z→A (1)
n 7→ n.1A 2.3 Résultats sur les corps finis
est un morphisme d’anneau. Il existe un entier n tel que ker(φ) = nZ. Cet entier n — La caractéristique d’un corps fini est nécéssairement un nombre premier.
s’appelle caractéristique de l’anneau A. — Pour p premier, pZZ
est un corps à p éléments, noté Fp
Proposition 25. La caractéristique d’un anneau unitaire intègre est 0 ou un nombre Définition 39. On introduit l’application
premier. F : Fp → Fp (2)
Application 26. p est premier ⇐⇒ Z
est intègre ⇐⇒ Z
est un corps. x 7→ xp
pZ pZ
. Il s’agit d’un morphisme de corps, appelé morphisme de Frobenius.
Théorème 27 (Théorème des restes chinois). Théorème des restes chinois ver-
Z
sion nZ . Théorème 40 (Existence et unicité des corps finis). — Soit F un corps fi-
nis, alors il existe p premier et n ∈ N tel que |F | = pn = q
Définition 28. On définit la fonction indicatrice d’Euler : ϕ(n) = Card({k ∈ — Soit p premier et n ∈ N. Alors le corps de décomposition de X q − X dans Fp
[1, n], | k ∧ n = 1}) est un corps finis à q éléments.
Remarque 29. ϕ(n) est aussi égal au nombre de générateur d’un groupe cyclique — Il est unique à isomorphisme près
Z ×
d’ordre n, où encore à Card(( nZ ) )
Corollaire 41. Soit F un corps à pn éléments. Soit A un sous-corps de F. A est un
Z ×
Définition 30. (( nZ ) ,×) est un groupe à φ(n) éléments, où φ est la fonction in- sous-corps de F de cardinal h ssi il existe d qui divise n tel que h = pd
dicatrice d’Euler. φ(n) est aussi égal au nombre de générateur d’un groupe cyclique
d’ordre n. Proposition 42. Eventuellement compter le nombre de carrés dans Fp ? Puis sym-
bole de Legendre vers la réciprocité quadratique.
Proposition 31. Si p est premier et n un entier naturel, φ(pn ) = pn−1 (p − 1)

Théorème 32 (Théorème chinois). — (n1 , ...nr ) sont premiers entre eux deux
à deux, ssi Z/(n1...nr )Z ' Z/n1 Z×...×Z/nr Z. On donne l’isomorphisme cor- 3 Applications aux polynômes dans Q[X]
respondant et son inverse !.
et Z[X]
Application 33. Multiplicativité de la fonction d’Euler.
3.1 Des critères d’irréductibilités
Théorème 34 (Euler et petit théorème de Fermat). — Soit k un entier
premier avec n un entier non-nul. Alors k φ(n) ≡ 1 [mod n]
Proposition 43. Soit p premier.
— Soit p un nombre premier et n un entier non-nul. Pour tout a ∈ Z, ap ≡
— Soit A et B dans Z[X], alors (A +¯ B)p = A¯p + B¯p dans Fp [X].
a [mod p] et ap−1 ≡ 1 [mod p] si pgcd(p, a) = 1
— Si A est dans Z[X] et B = Ap , alors on à l’égalité dans Fp [X] : B̄(X) = Ā(X p )
Application 35. Chiffrement RSA. n
X
Définition 44. Soit P = ak X k ∈ Z[X]. On appelle contenu de P l’entier
Théorème 36 (Wilson). Théorème de Wilson. Soit p> 1, p est premier ssi k=0
(p − 1)! ≡= −1 [mod p] c(p)=pgcd(a0 , ..., an ).
Proposition 45. — c(P Q) = c(P )c(Q) pour deux polynômes de Z[X]
— Soit P un polynôme de Z[X], de degré > 1. P est irreductible dans Z[X] ssi P
est de contenu 1 et P est irreductible dans Q[X]
— Si P,Q sont deux polynômes unitaires de Q[X] tel que le produit PQ soit dans
Z[X], alors P et Q sont dans Z[X]
n
X
Théorème 46 (Critère d’irreductibilité d’Eisenstein). Soit P = ak X k ∈
k=0
Z[X] et p un nombre premier. On suppose que p|ai ∀i ∈ {0, ..., n − 1}, p ne divise pas
an et p2 ne divise pas a0 . Alors P est un polynôme irreductible de Z[X]
Exemple 47. Pn (X) = X n − p est un polynôme irreductible de Q[X] de degré n.
Pn
Théorème 48 (Réduction modulo p).PRéduction modulo p. Soit P= i=0 ak X k
n
non constant dans Z[X], p premier, P̄ = i=0 a¯k X k . Si p ne divise pas an et P̄ est
irreductible dans Fp [X], alors P est irreductible dans Q[X]
Application 49. Le polynôme X 3 + 462X 2 + 2433X − 67691 est irreductible sur
Z[X] (et donc sur Q[X].

3.2 Les polynômes cyclotomiques

Définition 50. On définit le nème polynôme cyclotomique Φn tout en introduisant

Théorème 51. On a X n − 1 = Πd|n Φd (X) et Φn (X) est unitaire dans Z[X]

Application 52 (Progression arithmétique de Dirichlet). Soit a, n tel que

Théorème 53. Pour tout entier naturel n plus grand que 1, Φn est irreductible dans
Q[X], donc dans Q[X]
Application 54. Degré de l’extension cyclotomique. Soit ω une racine nème
première de l’unité, on a [Q(ω) : Q] = φ(n)