École AVOSZ

Connectez-vous

372. L’indicatrice d’Euler est une fonction multiplicative grâce au principe d’inclusion-exclusion

Yannis TRIANTAPHYLIDES

Soit $n$ un entier naturel supérieur ou égal à $2.$

En le décomposant comme produit de nombres premiers, vous constatez qu’il existe un entier naturel non nul $k$ ainsi que des entiers naturels non nuls $u_1, \dots, u_k$ et des nombres premiers $p_1,\dots,p_k$ deux à deux distincts tels que :

n = p_1^{u_1}\cdots p_k^{u_k} = \prod_{i=1}^k p_i^{u_i}.

Vous allez utiliser un outil de dénombrement pour calculer $\varphi(n)\comma$ où $\varphi$ désigne l’indicatrice d’Euler : $\varphi(n)$ est le nombre d’éléments de l’ensemble $A$ défini par :

A = \{m\in\llbracket 1, n\rrbracket, \pgcd(m, n)=1\}.

Notation $\#$

Pour tout ensemble $E\comma$ vous noterez $\# E$ le nombre d’éléments de $E.$

Utilisez le principe d’inclusion-exclusion (ou formule du crible)

Il est délicat de dénombrer directement les éléments de $A.$ Vous allez donc dénombrer à la place le complémentaire de $A$ dans $\llbracket 1, n\rrbracket\comma$ ce qui fournit :

n-\varphi(n) = \#\{m\in\llbracket 1, n\rrbracket, \pgcd(m, n)\neq1\}.

Vous notez $B$ l’ensemble défini par :

B= \{m\in\llbracket 1, n\rrbracket, \pgcd(m, n)\neq1\}.

Soit $m$ un élément de $B.$ Puisque $\pgcd(m,n)$ n’est pas égal à $1\comma$ il est supérieur ou égal à $2.$ Donc il existe un nombre premier $p$ tel que $p$ divise $\pgcd(m,n).$ Un tel $p$ divise $n.$ Compte tenu de la décomposition en produit de facteurs premiers de $n$ l’application du lemme d’Euclide permet d’affirmer qu’il existe un entier $i\in\llbracket 1, k\rrbracket$ tel que $p$ divise $p_i.$ Comme $p_i$ est un nombre premier, vous déduisez que $p\in\{1, p_i\}.$ Comme $p\neq 1$ en tant que nombre premier, vous avez $p = p_i.$

Comme $p$ divise $\pgcd(m,n)$ vous avez aussi $p$ qui divise $m.$ Or $p = p_i$ donc $p_i$ divise $m.$

Réciproquement, soit $i\in\llbracket 1, k\rrbracket$ tel que $p_i$ divise $m.$ Comme $p_i$ apparaît dans la décomposition de $n$ en produit de nombres premiers, vous déduisez que $p_i$ divise $n.$ Comme $p_i$ divise $m$ et $n$ à la fois, il divise $\pgcd(m,n).$ Comme $p_i$ est supérieur ou égal à $2$ en tant que nombre premier, vous déduisez $\pgcd(m,n)\neq 1.$

Vous avez donc établi que :

B = \{m\in\llbracket 1, n\rrbracket,\exists i\in\llbracket 1, k\rrbracket, p_i \mid m\}.

Cette écriture de $B$ suggère de définir, pour tout $i\in\llbracket 1, k\rrbracket$ l’ensemble suivant :

B_i=\{m\in\llbracket 1, n\rrbracket, p_i \mid m\}.

Vous avez ainsi :

B = \bigcup_{i=1}^k B_i.

Le nombre d’éléments de $B$ va être déterminé grâce au principe d’inclusion-exclusion (encore appelé formule du crible). Il vient :

\begin{align*} \#B &= \sum_{1\leq i \leq k} \#B_i-\sum_{\substack{1\leq i\leq k\\1\leq j\leq k\\i\lt j }}\#(B_i\cap B_j)+\cdots+(-1)^{k+1}\#(B_1\cap\cdots\cap B_k)\\ &=\sum_{u=1}^k (-1)^{u+1}\sum_{\substack{1\leq i_1\leq k\\ \dots\\ 1\leq i_u\leq k\\i_1\lt \cdots \lt i_u}}\#(B_{i_1}\cap\cdots\cap B_{i_u}). \end{align*}

Soit $u$ un nombre entier appartenant à l’intervalle $\llbracket 1, k\rrbracket$ et $(i_1,\dots,i_u)\in\llbracket 1, k\rrbracket^u$ tel que $i_1\lt\cdots \lt i_u.$ Par définition, vous avez :

B_{i_1}\cap\cdots\cap B_{i_u}=\{m\in\llbracket 1, n\rrbracket, \forall t\in\llbracket 1, u\rrbracket, p_{i_t} \mid m\}.

Comme $i_1\lt \cdots \lt i_u$ et que les nombres premiers $p_1,\dots,p_k$ sont deux à deux distincts, les nombres premiers $p_{i_1}, \dots, p_{i_u}$ sont deux à deux distincts. En particulier ils sont premiers entre eux deux à deux. Via le corollaire du théorème de Gauss, vous déduisez que :

B_{i_1}\cap\cdots\cap B_{i_u}=\{m\in\llbracket 1, n\rrbracket, p_{i_1}\cdots p_{i_u} \mid m\}.

Soit maintenant $x$ un élément de l’ensemble $B_{i_1}\cap\cdots\cap B_{i_u}.$ L’entier $x$ est compris entre $1$ et $n$ et le produit $p_{i_1}\cdots p_{i_u}$ divise $x.$ Donc il existe un entier naturel non nul $y$ tel que :

x = p_{i_1}\cdots p_{i_u} y.

Comme $x\leq n$ vous déduisez :

p_{i_1}\cdots p_{i_u} y \leq n.

La décomposition en facteurs premiers de $n$ montre que $\frac{n}{p_{i_1}\cdots p_{i_u}}$ est un nombre entier.

En effet :

\begin{align*} n & =\prod_{i=1}^k p_i^{u_i}\\ &= \prod_{i\in\{i_1,\dots, i_u\}} p_i^{u_i} \prod_{i\not\in \{i_1,\dots, i_u\}} p_i^{u_i}\\ &=p_{i_1}\cdots p_{i_u} \left( \prod_{i\in\{i_1,\dots, i_u\}} p_i^{u_i-1} \prod_{i\not\in \{i_1,\dots, i_u\}} p_i^{u_i}\right). \end{align*}

Comme $\forall i\in\llbracket 1, k\rrbracket, u_i \geq 1\comma$ le nombre $\prod_{i\in\{i_1,\dots, i_u\}} p_i^{u_i-1} \prod_{i\not\in \{i_1,\dots, i_u\}} p_i^{u_i}$ est bien un entier naturel non nul.

Par suite :

y\leq \frac{n}{p_{i_1}\cdots p_{i_u}}.

Comme $y$ est non nul, il vient :

1\leq y\leq \frac{n}{p_{i_1}\cdots p_{i_u}}.

Vous avez démontré l’inclusion :

B_{i_1}\cap\cdots\cap B_{i_u} \subset \left\{ p_{i_1}\cdots p_{i_u} y, y\in \left[ 1, \frac{n}{p_{i_1}\cdots p_{i_u}} \right]\cap \N\right\}.

Réciproquement, soit $y$ un nombre entier appartenant à l’intervalle $\left[ 1, \frac{n}{p_{i_1}\cdots p_{i_u}} \right].$

Note. Il est rappelé que $\frac{n}{p_{i_1}\cdots p_{i_u}}$ est un entier naturel non nul.

Par produit, le nombre $p_{i_1}\cdots p_{i_u} y$ est un entier naturel non nul. D’autre part, $p_{i_1}\cdots p_{i_u} y \leq n.$ Donc $p_{i_1}\cdots p_{i_u} y\in\llbracket 1, n\rrbracket.$ Le nombre $p_{i_1}\cdots p_{i_u} y$ est divisible par $p_{i_1}, \dots, p_{i_u}$ donc il appartient à $B_{i_1},\dots,B_{i_u}$ et il appartient à $B_{i_1}\cap\cdots\cap B_{i_u}.$

Vous avez donc l’égalité :

B_{i_1}\cap\cdots\cap B_{i_u} = \left\{ p_{i_1}\cdots p_{i_u} y, y\in \left[ 1, \frac{n}{p_{i_1}\cdots p_{i_u}} \right]\cap \N\right\}.

L’application $y\mapsto p_{i_1}\cdots p_{i_u}y$ étant injective, cette écriture montre que le nombre d’éléments de l’ensemble $B_{i_1}\cap\cdots\cap B_{i_u}$ est égal au nombre d’entiers de l’intervalle $\left[ 1, \frac{n}{p_{i_1}\cdots p_{i_u}} \right]\comma$ c’est-à-dire :

\boxed{\#(B_{i_1}\cap\cdots\cap B_{i_u}) = \frac{n}{p_{i_1}\cdots p_{i_u}}.}

À ce stade il a été démontré que :

\begin{align*} n-\varphi(n) &= \#B\\ &=\sum_{u=1}^k (-1)^{u+1}\sum_{\substack{1\leq i_1\leq k\\ \dots\\ 1\leq i_u\leq k\\i_1\lt \cdots \lt i_u}}\#(B_{i_1}\cap\cdots\cap B_{i_u})\\ &= \sum_{u=1}^k (-1)^{u+1} \sum_{\substack{1\leq i_1\leq k\\ \dots\\ 1\leq i_u\leq k\\i_1\lt \cdots \lt i_u}} \frac{n}{p_{i_1}\cdots p_{i_u}}. \end{align*}

Déterminez une expression de $\varphi(n)$

L’expression précédente se factorise par $n$ si bien que :

\begin{align*} n-\varphi(n) = n \left(\sum_{u=1}^k (-1)^{u+1} \sum_{\substack{1\leq i_1\leq k\\ \dots\\ 1\leq i_u\leq k\\i_1\lt \cdots \lt i_u}} \frac{1}{p_{i_1}\cdots p_{i_u}}\right). \end{align*}

En isolant $\varphi(n)$ vous déduisez :

\begin{align*} \varphi(n) &=n- n \left(\sum_{u=1}^k (-1)^{u+1} \sum_{\substack{1\leq i_1\leq k\\ \dots\\ 1\leq i_u\leq k\\i_1\lt \cdots \lt i_u}} \frac{1}{p_{i_1}\cdots p_{i_u}}\right)\\ &= n \left(1-\sum_{u=1}^k (-1)^{u+1} \sum_{\substack{1\leq i_1\leq k\\ \dots\\ 1\leq i_u\leq k\\i_1\lt \cdots \lt i_u}} \frac{1}{p_{i_1}\cdots p_{i_u}}\right)\\ &= n \left(1+\sum_{u=1}^k (-1)^{u} \sum_{\substack{1\leq i_1\leq k\\ \dots\\ 1\leq i_u\leq k\\i_1\lt \cdots \lt i_u}} \frac{1}{p_{i_1}\cdots p_{i_u}}\right). \end{align*}

Or, le développement du produit $\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$ est précisément égal à :

1+\sum_{u=1}^k (-1)^{u} \sum_{\substack{1\leq i_1\leq k\\ \dots\\ 1\leq i_u\leq k\\i_1\lt \cdots \lt i_u}} \frac{1}{p_{i_1}\cdots p_{i_u}}.

Donc vous avez démontré que :

\boxed{\varphi(n) = n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right).}

Déduisez-en que la fonction $\varphi$ est une fonction multiplicative

Soient $r$ et $s$ deux entiers supérieurs ou égaux à $2$ et premiers entre eux.

Vous décomposez $r$ en produit de nombres premiers. Il existe un entier naturel non nul $\kappa$ ainsi que des entiers naturels non nuls $\alpha_1, \dots, \alpha_{\kappa}$ et des nombres premiers $\xi_1,\dots,\xi_{\kappa}$ deux à deux distincts tels que :

r = \prod_{i=1}^{\kappa}\xi_i^{\alpha_i}.

Vous décomposez $s$ en produit de nombres premiers. Il existe un entier naturel non nul $\lambda$ ainsi que des entiers naturels non nuls $\beta_1, \dots, \beta_{\lambda}$ et des nombres premiers $\zeta_1,\dots, \zeta_{\lambda}$ deux à deux distincts tels que :

s = \prod_{j=1}^{\lambda}\zeta_j^{\beta_j}.

Comme $r$ et $s$ sont premiers entre eux, aucun nombre premier ne divise à la fois $r$ et $s.$ Quel que soit $(i,j)\in\llbracket 1, \kappa\rrbracket \times \llbracket 1, \lambda\rrbracket$ vous avez $\xi_i \neq \zeta _j.$ Donc vous avez directement la décomposition en produit de facteurs premiers du nombre $rs$ qui est :

rs = \left(\prod_{i=1}^{\kappa}\xi_i^{\alpha_i}\right) \left(\prod_{j=1}^{\lambda}\zeta_j^{\beta_j}\right).

Vous déduisez de cette écriture que :

\begin{align*} \varphi(rs) &= rs \prod_{i=1}^{\kappa}\left(1-\frac{1}{\xi_i}\right) \prod_{j=1}^{\lambda}\left(1-\frac{1}{\zeta_j}\right) \\ &=\left(r \prod_{i=1}^{\kappa} \left(1-\frac{1}{\xi_i}\right) \right)\left(s \prod_{j=1}^{\lambda} \left(1-\frac{1}{\zeta_j}\right) \right)\\ &=\varphi(r)\varphi(s). \end{align*}

Il reste le cas où l’un des deux entiers vaut $1.$ Comme $\llbracket 1, 1\rrbracket = \{1\}$ et $\pgcd(1,1)=1\comma$ vous avez $\varphi(1)=1.$ Si par exemple $r=1\comma$ alors $\varphi(rs) = \varphi(s) = \varphi(1)\varphi(s) = \varphi(r)\varphi(s).$ Le cas $s=1$ est identique.

Et vous concluez : l’indicatrice d’Euler $\varphi$ est multiplicative :

\boxed{\forall (r,s)\in(\NN)^2, \pgcd(r,s)=1 \implies\varphi(rs)=\varphi(r)\varphi(s).}