Problème Énoncé
La fonction indicatrice d’Euler
Rappels et notations
Soit n un entier strictement positif.
• Pour tous x, y de Z, on note x ≡ y [n] (et on dit que “x est congru à y modulo n”) si l’une des
conditions équivalentes suivantes est réalisée :
— L’entier n divise la différence x − y.
— Il existe k dans Z tel que y = x + kn.
— Les entiers x et y ont le même reste dans la division par n.
• La relation x ≡ y [n] est une relation d’équivalence sur Z.
On note x = {x + kn, k ∈ Z} la classe d’équivalence d’un élément x de Z.
On note Zn l’ensemble de toutes les classes d’équivalence.
L’ensemble Zn est de cardinal n. Plus précisément Zn = {0, 1, . . . , n − 1}.
• On définit deux lois sur Zn en posant : ∀ (x, y) ∈ Z, x + y = x + y et x y = xy.
Muni de ces deux lois, Zn possède une structure d’anneau commutatif.
On note Un le groupe multiplicatif des éléments inversibles de l’anneau Z.
• On note ϕ(n) le nombre d’entiers de {1, . . . , n} qui sont premiers avec n.
L’application ϕ : N∗ → N∗ est appelée indicateur d’Euler.
• On note m∧n (resp. m∨n) le plus grand commun diviseur (resp. le plus petit commun multiple)
de deux entiers m et n.
Énoncé
1. Soit p un nombre premier.
(a) Préciser la valeur de ϕ(p).
(b) Pour tout entier m > 1, montrer que ϕ(pm ) = pm − pm−1 .
2. (a) Soit a un entier relatif. Montrer que a ∈ Un ⇔ a ∧ n = 1.
Il en résulte que ϕ(n) est l’ordre (le cardinal) du groupe Un .
(b) Soit a un entier relatif, premier avec n. Montrer que aϕ(n) ≡ 1 [n].
On donnera deux démonstrations de ce résultat :
— La première en utilisant l’ordre de a dans la groupe Un .
— La seconde en justifiant que l’application x 7→ a x est une bijection de Un .
Quel résultat obtient-on quand n est un entier premier ?
(c) Montrer que pour tout n > 3, ϕ(n) est un entier pair.
3. On suppose n > 2. Montrer que les trois conditions suivantes sont équivalentes :
L’entier n est premier ; L’anneau Zn est un corps ; L’anneau Zn est intègre.
Page 1
Problème Énoncé
4. On se donne deux entiers a et b au hasard dans {1, . . . , n}.
n
P
Montrer que la probabilité pour que a ∧ b = 1 est pn = n12 2 ϕ(k) − 1 .
k=1
6
On admet que lim pn = π2 . On peut interpréter ce résultat en disant que la probabilité pour
n→+∞
que deux entiers a, b choisis au hasard soient premiers entre eux est π62 .
5. Dans cette question, m et n sont deux éléments de N∗ , premiers entre eux.
On note u et v deux entiers relatifs tels que um + vn = 1.
Pour tout x de Z, on note x la classe de x modulo mn (c’est-à-dire l’élément correspondant
dans l’ensemble Zmn ), x
b la classe de x modulo m, et x
e la classe de x modulo n.
(a) Montrer qu’on définit une application ψ de Zmn dans Zm × Zn en posant, pour tout entier
relatif x, ψ(x) = (b
x, x
e).
(b) Montrer que l’application ψ est un isomorphisme d’anneaux.
y , ze) de Um × Un , montrer que ψ −1 (b
(c) Pour tout (b y , ze) = x, avec x = umz + vny.
(d) Montrer que la restriction de ψ à Umn est une bijection de Umn sur Um × Un .
(e) En déduire l’égalité ϕ(mn) = ϕ(m)ϕ(n).
6. Pour tout n > 1, on note Pn l’ensemble des diviseurs premiers de n (en particulier P1 = ∅).
(a) Montrer que Pm ∩ Pn = Pm∧n et Pm ∪ Pn = Pm∨n = Pmn .
Que dire de Pm et Pn si m et n sont premiers entre eux ?
Q
(b) Pour tout n > 1, montrer que ϕ(n) = n 1 − p1 . Calculer ϕ(10!).
p∈Pn
(c) Pour tous entiers m, n > 1, montrer que ϕ(m)ϕ(n) 6 ϕ(mn), et qu’il n’y a égalité que
lorsque m et n sont premiers entre eux.
7. Dans cette question, on se donne m et n dans N∗ .
(a) Montrer que si m divise n, alors ϕ(m) divise ϕ(n).
(b) Montrer ϕ(m) ∨ ϕ(n) divise ϕ(m ∨ n) et que que ϕ(m ∧ n) divise ϕ(m) ∧ ϕ(n).
8. Dans cette question, on se donne n dans N∗ . On note Dn l’ensemble des diviseurs de n.
(a) On considère l’application f : {1, . . . , n} → Dn définie par f (k) = n ∧ k.
Montrer que chaque d de Dn possède exactement ϕ( nd ) antécédents par f .
P
(b) En déduire l’égalité ϕ(d) = n.
d∈Dn
(c) Pour tout k de N∗ , on définit µ(k) de la façon suivante :
— Si k est divisible par le carré d’au moins un entier premier, alors µ(k) = 0.
— Sinon µ(k) = (−1)m où m est le nombre de diviseurs premiers de k.
µ(d) nd .
P
Prouver l’égalité : ϕ(n) =
d∈Dn
Indication : raisonner par récurrence sur le nombre de diviseurs premiers de n.
Page 2
