Exercice 1 2655 Correction

Combien y a-t-il d’éléments inversibles dans $ℤ / 99 ℤ$ ?

Solution

Les inversibles dans $ℤ / 99 ℤ$ sont les classes associées aux entiers de ${1, \dots, 99}$ qui sont premiers avec $99 = 3^{2} \times 11$ . Il y en a

φ (99) = 99 \times (1 - \frac{1}{3}) (1 - \frac{1}{11}) = 3 \times 2 \times 10 = 60 .

Exercice 2 151 Correction

Pour $n \in ℕ^{*}$ , on note $φ (n)$ le nombre d’éléments inversibles dans $(ℤ / n ℤ, \times)$ .

(a)

Calculer $φ (p)$ et $φ (p^{α})$ pour $p$ premier et $α \in ℕ^{*}$ .
(b)

Soient $m$ et $n$ premiers entre eux.
On considère l’application $f : ℤ / m n ℤ \to ℤ / n ℤ \times ℤ / m ℤ$ définie par $f (\bar{x}) = (\hat{x}, \tilde{x})$ .
Montrer que $f$ est bien définie et réalise un isomorphisme d’anneaux.
(c)

En déduire que $φ (m n) = φ (m) φ (n)$ .
(d)

Exprimer $φ (n)$ selon la décomposition primaire de $n$ .

Solution

Les éléments inversibles de $(ℤ / n ℤ, \times)$ sont les éléments représentés par un nombre premier avec $n$ .

(a)

$φ (p) = p - 1$ . Être premier avec $p^{α}$ équivaut à être premier avec $p$ c’est-à-dire à ne pas être divisible par $p$ puisque $p \in 𝒫$ . Il y a $p^{α - 1}$ multiples de $p$ compris entre 1 et $p^{α}$ donc $φ (p^{α}) = p^{α} - p^{α - 1}$ .
(b)

Si $x = y [m n]$ alors $x = y [n]$ et $x = y [m]$ donc $f$ est bien définie.
$φ (\bar{1}) = (\hat{1}, \tilde{1})$ et si $a = x + y / x y [m n]$ alors $a = x + y / x y [n]$ donc $φ$ est un morphisme d’anneaux.
Si $f (\bar{x}) = f (\bar{y})$ alors $x = y [m]$ et $x = y [n]$ alors $m, n ∣ y - x$ et puisque $m \land n = 1$ alors $m n ∣ y - x$ donc $\bar{x} = \bar{y} [m n]$ .
$f$ est injective puis bijective par l’égalité des cardinaux.
(c)

Les inversibles de $ℤ / m n ℤ$ correspondent aux couples formés par un inversible de $ℤ / n ℤ$ et un inversible de $ℤ / m ℤ$ . Par suite, $φ (m n) = φ (m) φ (n)$ .
(d)

Si $n = \prod_{i = 1}^{N} p_{i}^{α_{i}}$ alors $φ (n) = \prod_{i = 1}^{N} p_{i}^{α_{i} - 1} (p_{i} - 1)$ .

Exercice 3 152 Correction

Pour $n \in ℕ^{*}$ , on note $φ (n)$ le nombre d’éléments inversibles dans $(ℤ / n ℤ, \times)$ .

Établir

\forall a \in {(ℤ / n ℤ)}^{*}, a^{φ (n)} = 1

où ${(ℤ / n ℤ)}^{*}$ désigne l’ensemble des inversibles de l’anneau $ℤ / n ℤ$ .

Solution

Soit $f : x \mapsto a x$ de ${(ℤ / n ℤ)}^{*}$ vers lui-même.

Cette application est bien définie, injective et finalement bijective par cardinalité.

Ainsi,

\prod_{x \in {(ℤ / n ℤ)}^{*}} x = \prod_{x \in {(ℤ / n ℤ)}^{*}} a x = a^{φ (n)} \prod_{x \in {(ℤ / n ℤ)}^{*}} x

puis $a^{φ (n)} = 1$ car l’élément $\prod_{x \in {(ℤ / n ℤ)}^{*}} x$ est inversible.

Plus directement, on peut aussi dire que ${(ℤ / n ℤ)}^{*}$ est un groupe multiplicatif à $φ (n)$ éléments et conclure.

Exercice 4 4241

Soient $a \in ℤ$ et $n \in ℕ$ avec $n \geq 2$ .

(a)

On suppose $a$ et $n$ premiers entre eux, montrer $a^{φ (n)} \equiv 1 [n]$ .
(b)

On suppose $a^{n - 1} \equiv 1 [n]$ et $a^{d} ／ \equiv 1 [n]$ pour tout entier naturel $d$ diviseur strict de $n - 1$ . Montrer que $n$ est un nombre premier.

Exercice 5 4061

Soient $a, n \in ℕ$ au moins égaux à $2$ et $N = a^{n} - 1$ . Montrer que $n$ divise $φ (N)$ .

Exercice 6 2374

Montrer que pour tout entier $n \geq 3$ , $φ (n)$ est un nombre pair.

Exercice 7 257 Correction

Établir

\forall n \geq 3, φ (n) \geq \frac{n \ln (2)}{\ln (n) + \ln (2)} .

Solution

Notons $p_{1}, \dots, p_{r}$ les facteurs premiers de $n$ . On sait

φ (n) = n (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{r}}) .

En ordonnant les $p_{1}, p_{2}, \dots, p_{r}$ , on peut affirmer

\forall 1 \leq i \leq r, p_{i} \geq 1 + i

et donc

(1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{r}}) \geq (1 - \frac{1}{2}) (1 - \frac{1}{3}) \dots (1 - \frac{1}{1 + r}) .

Par produit télescopique

(1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{r}}) > \frac{1}{2} \frac{2}{3} \dots \frac{r}{r + 1} = \frac{1}{r + 1} .

Or on a aussi

n \geq p_{1} \dots p_{r} \geq 2^{r}

et donc

r \leq \frac{n}{\ln (2)} .

On en déduit

φ (n) \geq \frac{n}{\frac{n}{\ln (2)} + 1} = \frac{n \ln (2)}{n + \ln (2)} .

Exercice 8 153 MINES (MP)Correction

Soit $n \in ℕ^{*}$ .

(a)

Soit $H$ est un sous-groupe de $(ℤ / n ℤ, +)$ . Montrer qu’il existe $a$ divisant $n$ vérifiant $H = ⟨ \bar{a} ⟩$ .
(b)

Observer que si $d ∣ n$ , il existe un unique sous-groupe de $(ℤ / n ℤ, +)$ de cardinal $d$ .
(c)

Justifier que si $d ∣ n$ , le groupe $(ℤ / n ℤ, +)$ possède exactement $φ (d)$ éléments d’ordre $d$ (avec $φ$ la fonction indicatrice d’Euler).
(d)

Montrer

$\sum_{d ∣ n} φ (d) = n .$

Solution

(a)

Soit $H$ un sous-groupe de $ℤ / n ℤ$ .

Si $H = {0}$ alors $H = ⟨ n ⟩$ .

Sinon, on peut introduire

$a = \min A avec A = {k \in ℕ^{*} | \bar{k} \in H} .$

On a $\bar{a} \in H$ donc $⟨ \bar{a} ⟩ \subset H$ .

La division euclidienne de $n$ par $a$ donne $n = q a + r$ avec $q \in ℤ$ et $r \in {0, \dots, a - 1}$ . On en déduit $\bar{r} = q . \bar{a} \in ⟨ \bar{a} ⟩ \subset H$ . Par définition de $a$ en tant que plus petit élément de $A$ , il vient $r = 0$ . Ainsi, $a ∣ n$ .

Soit $\bar{x} \in H$ . Par division euclidienne, on écrit $x = a q + r$ avec $q \in ℤ$ et $r \in {0, \dots, a - 1}$ . On en déduit $\bar{r} = \bar{x} - q . \bar{a} \in H$ . Par définition de $a$ en tant que plus petit élément de $A$ , il vient $r = 0$ puis $x = a q$ et donc $\bar{x} \in ⟨ \bar{a} ⟩$ . Par double inclusion, $H = ⟨ \bar{a} ⟩$ .
(b)

Si $a$ divise $n$ , on observe que $⟨ \bar{a} ⟩$ est de cardinal $n / a$ . Ainsi, $⟨ n / d ⟩$ est l’unique sous-groupe d’ordre $d$ de $(ℤ / n ℤ, +)$ .
(c)

Un élément d’ordre $d$ de $ℤ / n ℤ$ est générateur d’un sous-groupe à $d$ éléments donc générateur de $⟨ \bar{n / d} ⟩$ . Inversement, tout générateur de $⟨ \bar{n / d} ⟩$ est élément d’ordre $d$ de $ℤ / n ℤ$ . Or $⟨ \bar{n / d} ⟩$ est cyclique d’ordre $d$ donc isomorphe à $ℤ / d ℤ$ et possède ainsi $φ (d)$ générateurs. On peut alors affirmer que $ℤ / n ℤ$ possède exactement $φ (d)$ élément d’ordre $d$ .
(d)

L’ordre d’un élément de $ℤ / n ℤ$ est cardinal d’un sous-groupe de $ℤ / n ℤ$ et donc diviseur de $n$ . En dénombrant $ℤ / n ℤ$ selon l’ordre de ses éléments, on obtient

$\sum_{d ∣ n} φ (d) = n .$

Exercice 9 3634

Soit $n$ un entier naturel non nul.

(a)

Soit $d$ un diviseur positif de $n$ . Combien y a-t-il de $k \in ⟦ 1; n ⟧$ vérifiant $k \land n = d$ ?
(b)

En déduire

$n = \sum_{d ∣ n} φ (d)$

où la somme s’étend sur les diviseurs positifs $d$ de $n$ .

Exercice 10 5281 NAVALE (MP)Correction

On note $φ$ la fonction indicatrice d’Euler. Soit $n \in ℕ$ avec $n \geq 2$ .

(a)

Pour $d$ un diviseur de $n$ , montrer qu’il y a exactement $φ (d)$ éléments d’ordre $d$ dans le groupe $(ℤ / n ℤ, +)$ .
(b)

En déduire

$n = \sum_{d ∣ n} φ (d)$

où la somme s’étend sur les entiers $d$ diviseurs positifs de $n$ .
(c)

Écrire un programme employant cette formule pour calculer les valeurs de la fonction indicatrice d’Euler.

Solution

(a)

Soit $k \in ⟦ 1; n ⟧$ . L’ordre de $\bar{k}$ dans $ℤ / n ℤ$ est le plus petit entier $ℓ$ tel que $ℓ \bar{k} = \bar{0}$ , c’est-à-dire tel que $ℓ k$ soit un multiple de $n$ . L’ordre $ℓ$ de $\bar{k}$ apparaît donc comme le facteur qui mutliplie $k$ pour atteindre le ppcm de $k$ et $n$ ,

$ℓ = \frac{k \lor n}{k} = \frac{n}{k \land n} .$

L’élément $k$ est donc d’ordre $d$ si, et seulement si,

$k \land n = d^{'} avec d^{'} = \frac{n}{d} .$

Les entiers $k$ correspondant s’écrivent

$k = d^{'} k^{'} avec k^{'} \in ⟦ 1; d ⟧ et k^{'} \land d^{'} = 1 .$

Il y en a exactement $φ (d)$ .
(b)

Les ordres des éléments de $(ℤ / n ℤ, +)$ sont tous des diviseurs de $n$ et, en dénombrant $ℤ / n ℤ$ par regroupement de ses éléments selon leur ordre, il vient

$n = Card (ℤ / n ℤ) = \sum_{d ∣ n} Card {k \in ⟦ 1; n ⟧ | \bar{k} est d’ordre d} = \sum_{d ∣ n} φ (d) .$
(c)
Une programmation récursive emploie la formule qui précède sans être (a priori ?) plus efficace qu’un simple dénombrement des entiers compris entre $1$ et $n$ premier avec $n$
```
def phi(n):
    if n == 1:
        return 1
    S = 0
    for d in range(1,n):
        if n % d == 0:
            S = S + phi(d)
    return n - S
```

Exercice 11 2381

(Déterminant de Smith)

Soit $T = (t_{i, j}) \in ℳ_{n} (ℝ)$ la matrice de coefficients

t_{i, j} = {\begin{matrix} 1 & si i divise j \\ 0 & sinon. \end{matrix}

Aussi, soit $D \in ℳ_{n} (ℝ)$ la matrice diagonale de coefficients diagonaux $φ (1), \dots, φ (n)$ où $φ$ désigne la fonction indicatrice d’Euler.

(a)

Exprimer le coefficient d’indice $(i, j)$ de la matrice $T^{⊤} D T$ en fonction de $i \land j$ .
(b)

En déduire la valeur du déterminant de la matrice de Smith

$S = (\begin{matrix} 1 \land 1 & 1 \land 2 & \dots & 1 \land n \\ 2 \land 1 & 2 \land 2 & \dots & 2 \land n \\ ⋮ & ⋮ & ⋮ \\ n \land 1 & n \land 2 & \dots & n \land n \end{matrix}) .$

Exercice 12 5814 Correction

(Polynômes cyclotomiques)

On appelle racine primitive $n$ -ième de l’unité tout complexe $ξ$ générateur du groupe $(𝕌_{n}, \times)$ des racines $n$ -ième de l’unité. On note $Z_{n}$ l’ensemble des racines $n$ -ièmes de l’unité et l’on pose

Φ_{n} = \prod_{ξ \in Z_{n}} (X - ξ) .

(a)

Calculer $Φ_{n}$ pour $n = 1, 2, 3$ et $4$ .
(b)

Exprimer le degré de $Φ_{n}$ à l’aide de la fonction indicatrice d’Euler.
(c)

Calculer $Φ_{p}$ pour $p$ nombre premier. Donner $Φ_{5}$ .
(d)

Établir que pour tout $n \in ℕ$

$X^{n} - 1 = \prod_{k ∣ n} Φ_{k} .$

En déduire $Φ_{6}$
(e)

Soient $A$ et $B$ deux polynômes à coefficients entiers avec $B$ unitaire.

On suppose qu’il existe un polynôme $C$ tel que $A = B C$ . À l’aide d’un calcul de division euclidienne, établir que $C$ est à coefficients entiers.

En déduire que pour tout $k \in ℕ^{*}$ , le polynôme $Φ_{k}$ est à coefficients entiers.

Solution

(a)

Cas: $n = 1$ . Il n’y a qu’une seule racine primitive $1$ -ième de l’unité à savoir $ξ = 1$ . On a donc

$Φ_{1} = X - 1 .$

Cas: $n = 2$ . Il n’y a qu’une seule racine primitive $2$ -ième de l’unité à savoir $ξ = - 1$ . On a donc

$Φ_{2} = X + 1 .$

Cas: $n = 3$ . Il y a deux racines primitives $3$ -ièmes de l’unité qui sont $j$ et $j^{2}$ . On a donc

$Φ_{1} = (X - j) (X - j^{2}) = X^{2} + X + 1 .$

Cas: $n = 4$ . Il y a deux racines primitives $4$ -ièmes de l’unité qui sont $i$ et $- i$ . On a donc

$Φ_{1} = (X - i) (X + i) = X^{2} + 1 .$
(b)

Le nombre de générateurs du groupe cyclique $(𝕌_{n}, \times)$ est aussi le nombre de générateurs de $(ℤ / n ℤ, +)$ . Il y en a exactement $φ (n)$ avec $φ$ la fonction indicatrice d’Euler. On en déduit

$\deg (Φ_{n}) = φ_{n} .$
(c)

Si $p$ est un nombre premier, $φ (p) = p - 1$ . Sachant que $1$ n’est pas une racine primitive $p$ -ième de l’unité, toutes les autres racines $p$ -ièmes de l’unité sont primitives. On a donc

$Φ_{p} = \prod_{ξ \in 𝕌_{p} ∖ {1}} (X - ξ) = \frac{1}{X - 1} \prod_{ξ \in 𝕌_{p} ∖ {1}} (X - ξ) = \frac{X^{p} - 1}{X - 1} = 1 + X + \dots + X^{p - 1} .$

On en déduit

$Φ_{5} = 1 + X + X^{2} + X^{3} + X^{4} .$
(d)

Si $ξ$ est une racine $n$ -ième de l’unité, son ordre $k$ divise $n$ et celle-ci est une racine primitive $k$ -ième de l’unité. La réciproque est immédiate. En regroupant les racines $n$ -ième de l’unité selon leur ordre $k$ , on obtient

$\prod_{ξ \in 𝕌_{n}} = \prod_{k ∣ n} \prod_{ξ \in Z_{k}}$

autrement dit

$X^{n} - 1 = \prod_{k ∣ n} Φ_{k} .$

En particulier,

$X^{6} - 1 = Φ_{1} Φ_{2} Φ_{3} Φ_{6} = (X - 1) (X + 1) (X^{2} + X + 1) Φ_{6} .$

Or

$X^{6} - 1 = (X^{3} - 1) (X^{3} + 1) = (X - 1) (X^{2} + X + 1) (X + 1) (X^{2} - X + 1) .$

On en déduit

$Φ_{6} = X^{2} - X + 1 .$
(e)

$C$ apparaît comme le quotient de la division euclidienne de $A$ par $B$ . Lorsque l’on pose celle-ci, on n’opère que des multiplications et des soustractions sans aucune division car le polynôme $B$ est unitaire. Par conséquent, si les polynômes $A$ et $B$ sont à coefficients entiers, le polynôme $C$ est aussi à coefficients entiers par opérations sur les entiers.

Par récurrence forte sur $n \in ℕ^{*}$ , montrons que $Φ_{n}$ est à coefficients entiers.

Pour $n = 1$ , $Φ_{1} = X - 1$ est à coefficients entiers.

Supposons la propriété vraie jusqu’au rang $n - 1 \geq 1$ .

Au rang $n$ , on peut écrire

$X^{n} - 1 = \prod_{\binom{k ∣ n}{k \neq n}} Φ_{k} \times Φ_{n} .$

Le polynôme $X^{n} - 1$ est à coefficients entiers et, par hypothèse de récurrence forte, $\prod_{\binom{k ∣ n}{k \neq n}} Φ_{k}$ est à coefficients entiers. C’est aussi un polynôme unitaire par produit de polynômes unitaires. On peut donc affirmer que $Φ_{n}$ est à coefficients entiers.

La récurrence forte est établie.

Exercice 13 4151 CENTRALE (MP)Correction

Dans tout ce sujet $n$ désigne un naturel non nul.

On note $φ (n)$ l’indicatrice d’Euler de $n$ , $U_{n}$ l’ensemble des racines $n$ -ième de l’unité et $U_{n}^{*}$ l’ensemble des racines de l’unité d’ordre exactement $n$ . Enfin, pour $d \in ℕ^{*}$ , on pose

Φ_{d} = \prod_{z \in U_{d}^{*}} (X - z) .

(a)

Écrire en Python la fonction liste(n) qui renvoie

${k \in ⟦ 1; n ⟧ | k \land n = 1} .$

Écrire la fonction phi(n) qui renvoie $φ (n)$ puis sumphi(n) qui renvoie

$\sum_{d ∣ n} φ (d) .$
(b)

Montrer

$X^{n} - 1 = \prod_{d ∣ n} Φ_{d} .$
(c)

Justifier

$\sum_{d ∣ n} φ (d) = n .$
(d)

Montrer que $Φ_{n}$ est un polynôme à coefficients entiers.

On pose $Q_{n} = X^{n} - 1$ et l’on choisit $p, q, r$ des nombres premiers vérifiant

p < q < r < p + q .

On pose

n = p q r et R = \frac{Q_{p} Q_{q} Q_{r}}{X - 1} .

(e)

Montrer

$Φ_{n} = \frac{Q_{n} R}{Q_{p q} Q_{q r} Q_{r p}} .$
(f)

Montrer qu’il existe un polynôme $S$ tel que

$Φ_{n} - R = X^{p q} S .$
(g)

En déduire que le coefficient de $X^{r}$ dans $Φ_{n}$ est égal à $- 2$ .

Solution

(a)

On commence par définir une fonction calculant le pgcd de deux entiers

def gcd(a,b):
    if a % b == 0:  return b
    else: return gcd(b, a % b)
def liste(n):
    L = []
    for k in range(1,n):
        if gcd(n,k) == 1: L.append(k)
    return L
def phi(n):
    return len(liste(n))
def sumphi(n):
    return sum(liste(n))

(b)

$U_{n}$ est un groupe à $n$ . Les éléments de ce groupe ont un ordre divisant $n$ et pour tout $d$ divisant $n$ , les éléments du groupe $U_{n}$ d’ordre $d$ sont exactement ceux de $U_{d}^{*}$ . On en déduit que $U_{n}$ est la réunion disjointe des $U_{d}^{*}$ pour $d$ parcourant les diviseurs de $n$ . On en déduit

$X^{n} - 1 = \prod_{z \in U_{d}} (X - z) = \prod_{d ∣ n} Φ_{d} .$
(c)

Le polynôme $Φ_{n}$ est de degré $φ (n)$ car les racines de l’unité d’ordre $n$ sont les

$e^{2 i k π / n} avec k \in ⟦ 1; n ⟧, k \land n = 1 .$

L’identité précédente donne la relation voulue en passant celle-ci au degré.
(d)

Par récurrence forte sur l’entier $n \geq 1$ .

La propriété est immédiate quand $n = 1$ . Supposons la propriété vérifiée jusqu’au rang $n - 1$ .

On a

$X^{n} - 1 = \prod_{d ∣ n, d \neq n} Φ_{d} \times Φ_{n} .$

Le polynôme $X^{n} - 1$ est à coefficients entiers et $\prod_{d ∣ n, d \neq n}$ l’est aussi. De plus, le coefficient dominant de ce dernier vaut $1$ . On réalisant une division euclidienne, le calcul de $Φ_{n}$ détermine un polynôme à coefficients entiers.
(e)

Les diviseurs de $n$ sont $1, p, q, r, p q, q r, r p$ et $n$ donc

$Q_{n} = (X - 1) Φ_{p} Φ_{q} Φ_{r} Φ_{p q} Φ_{q r} Φ_{r p} Φ_{n} .$

De même

$Q_{p q} = (X - 1) Φ_{p} Φ_{q} Φ_{p q}, etc.$

La relation demandée s’en déduit.
(f)

Par ce qui précède, on peut écrire

$(Φ_{n} - R) Q_{p q} Q_{q r} Q_{r p} = R (Q_{n} - Q_{p q} Q_{q r} Q_{r p})$

$0$ n’est pas racine de $Q_{p q} Q_{q r} Q_{r p}$ , ni de $R$ , mais

$Q_{n} - Q_{p q} Q_{q r} Q_{r p} = X^{p q} + \dots$

On en déduit que $0$ est racine de multiplicité $p q$ de $Φ_{n} - R$ .
(g)

Puisque $r < p q$ , le coefficient de $X^{r}$ dans $Φ_{n}$ est celui de $X^{r}$ dans $P$ . Or

$P$ $= (X^{p} - 1) (X^{q} - 1) (1 + X + \dots + X^{r - 1})$

$= (1 - X^{p} - X^{q} + X^{p + q}) (1 + X + \dots + X^{r - 1}) .$

Le coefficient de $X^{r}$ dans ce polynôme est $- 2$ car $p + q > r$ .

[<] Équations modulaires, théorème chinois

Édité le 26-01-2024

	$P$	$= (X^{p} - 1) (X^{q} - 1) (1 + X + \dots + X^{r - 1})$
		$= (1 - X^{p} - X^{q} + X^{p + q}) (1 + X + \dots + X^{r - 1}) .$

Indicatrice d'Euler