Lycée Louis-Le-Grand, Paris Pour le 15/03/2024

MP2I – Mathématiques
A. Troesch

DM no 18 : Arithmétique

Suggestion de travail supplémentaire (à ne pas me rendre) : Le problème 15 de la sélection, sur des tests de
primalité. Très beau problème non trivial, passant par un certain nombre de techniques algébriques. La problématique
est cruciale dans le domaine de l’informatique, puisque les tests de primalité et les problèmes de factorisation sont au
coeur de la cryptographie.
Problème 1 – Nombres de Carmichael

Le but de ce problème est d’étudier certaines propriétés des nombres de Carmichael, nombres composées qui satisfont
tout de même la propriété du petit théorème de Fermat. Notre but est notamment de donner une caractérisation des
˚
nombres de Carmichael en fonction de l’indicateur de Carmichael λpGq, défini comme l’exposant du groupe pZ{nZq
des éléments inversibles de l’anneau Z{nZ, donc comme le ppcm des ordres des éléments de ce groupe. Pour étudier cet
indicateur de Carmichael, nous commençons par l’étude des groupes pZ{nZq˚ , éléments inversibles de l’anneau Z{nZ.

Partie I – Structure du groupe pZ{pZq˚

Soit p un nombre premier. On montre dans cette partie que le groupe ppZ{pZq˚ , ˆq des éléments inversibles du corps
Fp “ Z{pZ est cyclique d’ordre p ´ 1, donc isomorphe à pZ{pp ´ 1qZ, `q ou encore à pUp´1 , ˆq. Un générateur de ce
groupe est appelé racine primitive modulo p. On admettra dans cette partie que si P est un polynôme à coefficients
dans un corps K et si r est une racine de P , alors P est divisible par pX ´ rq : autrement dit, il existe un polyôme Q
tel que P pXq “ pX ´ rqQpXq.

1. Soit pG, ˆq un groupe abélien fini, et x et y deux éléments de G d’ordre a et b. Montrer qu’il existe deux
éléments x1 et y 1 d’ordre a1 et b1 tels que a1 ^ b1 “ 1 et a1 b1 “ a _ b.
2. En considérant x1 y 1 , en déduire l’existence d’un élément d’ordre a _ b.
3. Soit ωpGq le ppcm des ordres de tous les éléments de G. Montrer qu’il existe un élément g P G d’ordre ωpGq.
En déduire que
ωpGq “ mintk P N˚ | @g P G, g k “ 1, u
où 1 désigne le neutre de G.
4. Soit G “ ppZ{pZq˚ , ˆq. Justifier que l’ordre de G est p ´ 1.
5. Soit P P Fp rXs le polynôme à coefficients dans Fp défini par :

P pXq “ X ωpGq ´ 1.
ź
Montrer que pour tout ξ P G, P pξq “ 0, et en déduire que P pXq est divisible par pX ´ ξq
ξPG
6. En déduire que p ´ 1 ď ωpGq, puis que ωpGq “ p ´ 1.
7. Montrer que G est cyclique d’ordre p ´ 1.
On peut remarquer que la preuve ci-dessus s’adapte sans difficulté pour montrer plus généralement que pour tout
corps fini K, K ˚ est un groupe cyclique, formé des racines du polynôme X n´1 ´ 1, n étant l’ordre de K.

Partie II – Stucture des groupes pZ{pn Zqˆ

Soit p un entier premier impair et n P N˚ , n ě 2. On généralise le résultat de la partie I en montrant dans cette partie
que le groupe ppZ{pn Zqˆ , ˆq des éléments inversibles de l’anneau Z{pn Z est cyclique.

1. Soit k P Z, et k son représentant dans Z{pn Z. Montrer que k est inversible si et seulement si k n’est pas divisible
par p.

1
 2. En déduire que pZ{pn Zqˆ est d’ordre pn´1 pp ´ 1q.
3. Montrer que pour tout a P Z, et tout m P N˚ , p1 ` pm aqp ” 1 ` pm`1 a rpm`2 s.
m
4. En déduire que pour tout a P Z, et tout m P N, p1 ` paqp ” 1 ` pm`1 a rpm`2 s.
5. Montrer que 1 ` p est d’ordre pn´1 dans pZ{pn Zqˆ
6. En considérant une racine primitive modulo p, montrer qu’il existe un élément d’ordre p ´ 1 dans pZ{pn Zqˆ .
7. En déduire que pZ{pn Zqˆ est cyclique d’ordre pn´1 pp ´ 1q.

Partie III – Cas des pZ{2n Zqˆ

On termine cette étude avec le cas p “ 2.
1. On suppose n ě 3. On note G “ pZ{2n Zqˆ , H l’ensemble des classes modulo 2n des entiers k congrus à 1
modulo 4, et et K “ pt´1, `1u, ˆq.
(a) Montrer que H est un sous-groupe de G. Quel est son ordre ?
(b) Exhiber un isomorphisme de H ˆ K ÝÑ G
n´3
(c) Montrer que 52 ” 1 ` 2n´1 r2n s, et en déduire que l’ordre de 5 dans H est 2n´2 .
(d) En déduire que le groupe multiplicatif G est isomorphe au groupe additif pZ{2ZqˆpZ{2n´2Zq. Est-il cyclique ?
ˆ
2. Décrire les groupes pZ{2n Zq pour n P t1, 2u.

Partie IV – Nombres de Carmichael et indicateur de Carmichael

On appelle nombre de Carmichael un nombre composé n tel que pour tout entier a premier avec n, on ait an´1 ” 1 rns.
On rappelle que l’exposant d’un groupe abélien fini G est le ppcm de l’ordre de tous les éléments du groupe G, et que
la question III-2 permet de justifer l’existence d’un élément x P G dont l’ordre est égal à l’exposant de G. On définit
l’indicateur λpnq de Carmichael d’un entier n ą 1 comme étant égal à l’exposant de ppZ{nZqˆ , ˆq. On rappelle enfin
que pour tout n ě 1, ϕpnq est le nombre d’entiers premiers avec n dans v1, nw.
1. Justifier que pour tout n ě 2, λpnq divise ϕpnq, avec égalité si et seulement si pZ{nZq˚ est cyclique.
2. Justifier que n est un nombre de Carmichael si et seulement si λpnq divise strictement n ´ 1.
k
ź
3. Montrer que pour tout n “ pα
i avec αi ě 1 et k ě 1, on a
i

i“1

λpnq “ λppα α2 αk
1 q _ λpp2 q _ ¨ ¨ ¨ _ λppk q.
1

4. En déduire une expression explicite de λpnq en fonction des facteurs premiers de n, en distinguant suivant que
8 divise n ou non (on ne cherchera pas à expliciter les ppcm intervenant dans cette formule)
5. À l’aide des questions précédentes, montrer que n est un nombre de Carmichael si et seulement si n est composé,
sans facteur multiple ( i.e. vp pnq “ 0 ou 1 pour tout p premier), et pour tout facteur premier p de n, p ´ 1
divise n ´ 1.
6. Montrer que 561 est un nombre de Carmichael.
7. Montrer que n est de Carmichael si et seulement si n est composé, et pour tout a P Z, an ” arns.

Problème 2 – Postulat de Bertrand, théorème de Sylvester

Le but de ce problème est de démontrer le postulat de Joseph Bertrand (1822-1900, mathématicien et économiste
français, beau-frère de Charles Hermite), stipulant que pour tout n P N˚ , il existe un nombre premier dans l’ensemble
vn ` 1, 2nw. Ce postulat a été démontré en 1850 par Pafnouti Tchebychev (celui des polynômes). La preuve que nous
proposons ici est due au mathématicien hongrois Paul Erdös (1913-1996).

Partie I – Majoration du produit des premiers nombres premiers

Soit P l’ensemble des nombres premiers, et n P N˚ .
ˆ ˙ ˆ ˙ ˆ ˙
2n ` 1 2n ` 1 2n ` 1
1. En comparant et , montrer que ď 22n .
n n`1 n

2
 ˆ ˙
ź 2n ` 1
2. Montrer que p divise
pPP
n
n`1ăpď2n`1
ź
3. En raisonnant par récurrence sur m, montrer que pour tout m ě 2 : p ď 4m´1
pPP
pďm

Partie II – Majoration d’un coefficient binomial

Soit n P N, n ą 2.
1. Montrer que pour tout réel positif x, t2xu ´ 2txu P t0, 1u.
2. Montrer que pour tout nombre premier p, et tout entier naturel N , la valuation p-adique de N ! est
ÿ ZN ^
vp pN !q “
kě1
pk

(formule de Legendre).
3. En déduire que :
(a) pour tout nombre premier p, pvp pp n qq ď 2n ;
2n

?
ˆˆ ˙˙
2n
(b) pour tout nombre premier p ą 2n, vp ď1
n
ˆˆ ˙˙
2 2n
(c) pour tout nombre premier p tel que n ă p ď n, vp “ 0 (la clé de la preuve, selon Erdös).
3 n
4. En déduire que : ¨ ˛ ¨ ˛
?
ˆ ˙
2n ˚ ź ‹ ˚ ź
ď p2nq 2n ˚ ‚¨ ˝
p‹ p‚.
‹
n ˝
pPP pPP
?
2năpď 23 n năpď2n

Partie III – Démonstration du postulat de Bertrand

Soit n P N, n ě 2. On suppose dans cette partie que l’ensemble vn ` 1, 2nw ne contient aucun nombre premier.
ˆ ˙ ˆ ˙
2n 2n
1. (a) Montrer que pour tout entier naturel k ă n, on a ă .
k k`1
4n
ˆ ˙
2n
(b) En déduire que ď .
2n n
2. En déduire que :
4n ? 2
ď p2nq 2n 4 3 n .
2n
3. (a) Justifier que pour tout réel a ą 1, a ` 1 ă 2a .
?
6
(b) Montrer que 2n ď 26 2n
.
2{3
4. Montrer que, sous l’hypothèse faite en début de partie, pour tout n ě 50, 22n ă 220p2nq . En déduire que
n ă 4000.
5. En remarquant que 2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503, 4001 sont premiers, démontrer que le postu-
lat de Bertrand est vrai pour n ď 4000.
6. Conclure.

Partie IV – Une conséquence du théorème de Sylvester

Le théorème de Sylvester ci-dessous constitue une généralisation du postulat de Bertrand : Si n et k sont deux entiers
strictement positifs tels que n ě 2k, alors l’un au moins des nombres n, n ´ 1, . . . , n ´ k ` 1 possède un diviseur premier
strictement plus grand que k.
1. Montrer que le théorème de Sylvester pour n “ 2k est équivalent au postulat de Bertrand.

3
Dans la suite du problème, on admet le théorème de Sylvester, et on en donne un conséquence ˆ ˙assez inattendue :
n
les coefficients binomiaux ne sont presque jamais des puissances. Plus précisément, l’équation “ mℓ n’a pas de
k
solution entière en m dès lors que ℓ ě 2 et 4 ď k ď n ´ 4. La preuve exposée ci-dessous est également due à Erdös.
2. Justifier qu’on peut se limiter à l’étude du cas où n ě 2k. On suppose désormais cette condition satisfaite.
ˆ ˙
n
3. Montrer que possède un facteur premier p ą k.
k
4. Soit n, k dans N˚ tels que n ě 2k. Supposons qu’il existe un entier m, et un entier ℓ ě 2 tels que nk “ mℓ
` ˘

(a) Montrer qu’il existe un entier premier p et un entier i P v0, k ´ 1w tel que pℓ divise n ´ i.
(b) En déduire que n ě k ℓ .
5. (a) Justifier l’existence et l’unicité de couples d’entiers positifs pai , mi q, tels que les ai sont non divisibles par
une puissance non triviale d’ordre ℓ, et tels que pour tout i P v0, k ´ 1w, n ´ i “ ai mℓi
(b) Montrer que les ai , i P v0, k ´ 1w sont deux à deux distincts.
Indication : si ce n’est pas
ble cas, considérer ai ?
“ aj , avec i ă j. En remarquant que mi ě mj ` 1, montrer
que pn ´ iq ´ pn ´ jq ą ℓ aj mj , puis que k ą n.
ℓ

6. (La clé de la preuve, selon Erdös)

k´1
(a) Montrer qu’il existe u et v des entiers premiers entre eux tels que uℓ ai “ v ℓ k!.
ś
i“0
(b) Montrer que tout diviseur premier p de v vérifie p ď k.
(c) Soit p un diviseur premier de v. Montrer que
ℓ´1
ÿ ˆZ ^ ˙
k
vp pa0 a1 . . . ak´1 q ď ` 1
i“1
pi

(d) À l’aide de la formule de Legendre, en déduire que

vp pv ℓ q ď ℓ ´ 1.

puis que v “ 1.
(e) Montrer que σ : i ÞÑ ai est une bijection de v0, k ´ 1w dans v1, kw. On note τ sa réciproque.
7. Montrer que si ℓ “ 2, ˆ
le résultat
˙ attendu est vrai (donc que pour tout k ě 4 et n ě 2k, il n’existe pas de solution
n
entière de l’équation “ m2 ).
k
8. On suppose ℓ ě 3, et k ě 4. Soit i1 “ τ p1q, i2 “ τ p2q et i4 “ τ p4q.
(a) Montrer que pn ´ i2 q2 ‰ pn ´ i1 qpn ´ i4 q
Indication : Poser b, x, y tels que n ´ i2 “ b, n ´ i1 “ b ´ x, n ´ i4 “ b ` y, et montrer que si l’égalité est
vraie, py ´ xqb “ xy, puis en minorant |xy|, trouver, à l’aide de la question 3, |xy| ą |xy|.
(b) En déduire que m2i2 ‰ mi1 mi4 .
(c) On suppose m2i2 ą mi1 mi4 . Montrer successivement :
i. 2pk ´ 1qn ą pn ´ i2 q2 ´ pn ´ i1 qpn ´ i4 q ą 4ℓpmi1 mi4 qℓ´1
ii. 2pk ´ 1qnmi1 mi4 ą ℓpn ´ k ` 1q2 ą 2n2 (on pourra remarquer que n ą 6k)
2
iii. kn 3 ą n
(d) Conclure dans le cas où m2i2 ą mi1 mi4 .
(e) Terminer la preuve du résultat.
9. (Question pouvant être traitée séparément ; de la nécessité de l’hypothèse k ě 4)
Soit pun qnPN définie par u0 “ 9 et pour tout n P N, un`1 “ p2un ´ 1q2 .
(a) Montrer que pour tout n P N, u2n est un carré parfait.
` ˘

(b) En déduire que l’équation n2 “ m2 , d’inconnues entières n et m, admet une infinité de solutions.
` ˘

(c) Montrer que 50

` ˘
3 est un carré parfait. On sait montrer que c’est la seule solution pour k “ 3 et ℓ “ 2.
Ainsi, l’hypothèse k ě 4 est importante dans la preuve générale. Où s’en est-on servi ?