MPSI 2024 DM 11
Partie I
Dans toute cette partie, n désigne un entier naturel non nul. On rappelle que (Z/nZ, +, ×) est
un anneau commutatif de cardinal n. Pour tout entier relatif a, on note a la classe de a modulo
n.
1. Soit a ∈ Z vérifiant a ∧ n = 1.
(a) Montrer qu’il existe deux entiers relatifs b et v tels que ab + nv = 1.
(b) Montrer que a × b = 1. Qu’en déduit-on pour l’élément a de l’anneau Z/nZ ?
(c) Dans cette question uniquement, on prend n = 2025. Quel est l’inverse dans Z/nZ de
l’élément 1492 ?
(d) Soit maintenant a ∈ Z vérifiant a ∧ n = δ 6= 1. Soit b = nδ ∈ Z \ {0}. Que vaut a × b ?
En déduire que a n’est pas inversible dans l’anneau Z/nZ.
On vient de démontrer qu’un élément x = a de Z/nZ est inversible si et seulement si
a ∧ n = 1. On note dorénavant Un l’ensemble des éléments inversibles de Z/nZ. On pose
également ϕ(n) = card Un . La fonction ϕ est appelée la fonction indicatrice d’Euler. À
titre d’exemple, ϕ(1) = ϕ(2) = 1, ϕ(3) = ϕ(4) = 2, ϕ(5) = 4 et ϕ(6) = 2.
2. On suppose donnée une fonction pgcd renvoyant le pgcd de deux entiers. Écrire une
fonction phi_naive prenant en paramètre un entier n ≥ 1 et renvoyant ϕ(n).
3. Donner dans un tableau la valeur de ϕ(n) pour n ∈ J1, 20K.
Partie II
Dans cette partie, on établit une formule donnant la valeur de ϕ(n) pour tout entier n ≥ 2.
1. Soit p un nombre premier.
(a) Calculer ϕ(p).
(b) Plus généralement, calculer ϕ(pα ) pour tout entier naturel non nul α.
2. On se donne deux entiers naturels non nuls a et b premiers entre-eux . Pour tout entier
relatif x, on note x la classe de x modulo ab, x̂ la classe de x modulo a, et x̃ la classe de
x modulo b. On considère l’application
f : Z/abZ → Z/aZ × Z/bZ
définie pour tout x ∈ Z par
f (x) = (x̂, x̃)
(a) Soient x, x0 ∈ Z vérifiant simultanément x ≡ x0 mod a et x ≡ x0 mod b.
i. Montrer que x ≡ x0 mod ab.
ii. Que vient-on de montrer à propos de la fonction f ?
(b) Soient α et β deux entiers relatifs.
i. Soient u, v ∈ Z tels que ua + vb = 1 (l’existence de tels entiers u et v est assurée
par le théorème de Bézout). Soit x0 = uaβ + vbα. Montrer que x0 ≡ α mod a et
x0 ≡ β mod b.
1
ii. En déduire le théorème des restes chinois : f est surjective.
iii. Écrire une fonction chinois prenant en paramètres 4 entiers a, b, α, β et telle que,
si a et b sont premiers entre-eux, l’appel chinois(a, b, alpha, beta) renvoie
l’unique entier x ∈ J0, ab − 1|K tel que x ≡ α mod a et x ≡ β mod b.
(c) Soit x ∈ Z/abZ. Montrer que si x ∈ Uab alors f (x) ∈ Ua × Ub .
On peut donc considérer la fonction g : Uab → Ua × Ub définie par g(x) = f (x) pour
tout x ∈ Uab .
(d) En utilisant l’injectivité de f , prouver que g est injective.
(e) Soit (α, β) ∈ Ua × Ub . Soit x ∈ Z/abZ l’unique antécédent de (α, β) par f . Montrer
que x ∈ Uab et en déduire que (α, β) a un antécédent par g.
(f) L’application g est donc bijective. En déduire que ϕ(ab) = ϕ(a)ϕ(b).
3. Soit n un entier naturel supérieur ou égal à 2. On écrit n sous la forme n = pα1 1 . . . pαk k où
les pi sont des nombres premiers distincts et les αi des entiers naturels non nuls. Montrer
que
1 1
ϕ(n) = n 1 − ... 1 −
p1 pk
4. Que valent ϕ(2024) ? ϕ(2025) ?
5. On suppose donnée une fonction facteurs_premiers prenant en paramètre un entier
n ≥ 1 et telle qu’un appel à facteurs_premiers(n) renvoie, en reprenant les notations
de la question 3, la liste [(p1 , α1 ), . . . , (pk , αk )]. Écrire une fonction euler_phi prenant en
paramètre un entier n ≥ 1 et renvoyant ϕ(n).
Partie III
Ce qui précède montre que si l’on sait décomposer n en produit de facteurs premiers, alors on sait
calculer ϕ(n). On se pose dans cette partie la question de la réciproque : si l’on sait calculer ϕ(n),
sait-on décomposer n en produit de facteurs premiers ? . On donne dans ce qui suit la réponse à
cette question dans un cas particulier.
On se donne un entier n ≥ 2. On suppose que n = pq où p et q sont deux nombres premiers
distincts.
1. Déterminer ϕ(n) en fonction de p et q, et en déduire p + q en fonction de n et de ϕ(n).
2. Montrer que p et q sont les racines d’une équation du second degré dont les coefficients
ne dépendent que de n et de ϕ(n).
3. Écrire une fonction decomposer prenant en paramètres deux entiers n et v, et telle que si
n = pq est le produit de deux nombres premiers distincts p et q, et v = ϕ(n), alors l’appel
decomposer(n,v) renvoie le couple (p, q).
4. L’entier
n = 124702704813441811944131913231501396808839604840033
est le produit de 2 nombres premiers p et q. Sachant que
ϕ(n) = 124702704813441811944131890897145841253284150406660
que valent p et q ?