344. L’indicatrice d’Euler est une fonction multiplicative

Dans ce contenu, les notions d’anneaux et d’ensemble-quotient ne seront pas abordées. L’approche choisie consiste à démontrer la multiplicativité de l’indicatrice d’Euler en travaillant principalement dans l’ensemble $\Z$ des entiers relatifs.

Notations

Pour tout entier naturel $a$ et tout entier naturel $n$ non nul, la notation $(a \mod n)$ désignera le reste de la division euclidienne de $a$ par $n.$

Pour tout entier naturel $n$ non nul, vous notez $\varphi(n)$ le nombre d’éléments de l’ensemble :

U_n = \{k\in\Z, \pgcd(k,n)=1\text{ et } 0\leq k\leq n-1\}.

Il s’agit de démontrer que si $m$ et $n$ sont deux entiers naturels non nuls tels que $\pgcd(m,n)=1\comma$ alors :

\varphi(mn)=\varphi(m)\varphi(n).

Dans toute la suite de ce contenu, vous fixez deux entiers naturels non nuls $m$ et $n$ tels que $\pgcd(m,n)=1.$

Construisez une application de l’ensemble $U_{mn}$ vers le produit $U_m\times U_n$

Soit $x$ un élément de $U_{mn}.$

Pour être certain d’obtenir un entier de l’ensemble $U_m$ et un entier de l’ensemble $U_n$ vous effectuez la division euclidienne de $x$ par $m$ et par $n$ respectivement. Il existe quatre entiers uniques $q_n, r_n, q_m, r_m$ avec $0\leq r_n\leq n-1$ et $0\leq r_m\leq m-1$ tels que :

\left\{\begin{align*} x&=q_m m+r_m\\ x&=q_n n+r_n. \end{align*} \right.

Il s’agit maintenant de comprendre pourquoi le couple $(r_m,r_n)$ est un élément de l’ensemble $U_m\times U_n.$

Notez $d = \pgcd(r_m,m).$ Comme $d$ divise $m\comma$ $d$ divise le produit $q_m m.$ Comme $d$ divise aussi $r_m\comma$ il divise la somme $q_m m + r_m.$ Par suite, $d$ divise $x.$

Comme $d$ divise $m$ et que $m$ divise le produit $mn$ vous déduisez que $d$ divise $mn.$ Comme $d$ divise $mn$ et $x\comma$ c’est un diviseur commun à $x$ et à $mn.$ Or, $x\in U_{mn}$ donc $\pgcd(x,mn) = 1.$ Il en résulte que $d=1.$

Il est ainsi démontré que $\pgcd(r_m,m) = 1.$ Vu que $0\leq r_m\leq m-1$ vous déduisez $\boxed{r_m\in U_m.}$

Un raisonnement identique permet d’aboutir à la conclusion $\boxed{r_n\in U_n.}$

Par le procédé décrit ci-dessus, vous avez défini une application $f$ qui va de $U_{mn}$ dans $U_m\times U_n.$ Elle est définie, pour tout entier $k\in U_{mn}\comma$ par :

f(k) = ((k\mod m) , (k\mod n)).

Démontrez l’injectivité de cette application

Soient $x$ et $y$ deux éléments de $U_{mn}$ tels que $f(x) = f(y).$

Alors :

\begin{align*} (x\mod m) &= (y\mod m)\\ (x\mod n) &= (y\mod n). \end{align*}

Quand vous effectuez la division euclidienne de $x$ par $m\comma$ puis celle de $y$ par $m\comma$ vous constatez qu’il existe un couple $(q_x,q_y)$ d’entiers tel que :

\begin{align*} x &= q_x m+(x\mod m)\\ y &= q_y m + (y\mod m). \end{align*}

Comme $(x\mod m) = (y\mod m)\comma$ par soustraction, vous déduisez :

x-y = q_xm-q_ym = m(q_x-q_y).

Ainsi l’entier $m$ divise la différence $x-y.$

En suivant un raisonnement similaire pour $n\comma$ vous aboutissez au fait que $n$ divise aussi la différence $x-y.$

D’après ces constats, il existe deux entiers $m’$ et $n’$ tels que :

\begin{align*} x-y &= mm'\\ x-y&=nn'. \end{align*}

Vous déduisez $mm’ = nn’$ puis $n \mid mm’.$ Comme $\pgcd(m,n)=1$ le théorème de Gauss fournit $n \mid m’.$ Donc il existe un entier $k$ tel que $m’ = kn.$

L’égalité $x-y = mm’$ devient $x-y = mkn$ si bien que le produit $mn$ divise $x-y.$

Supposez, en raisonnant par l’absurde, que $k$ soit non nul, ce qui implique $\vert k \vert \geq 1.$

Du coup, $\vert x-y \vert = \vert k \vert \times mn$ d’où $\vert x-y\vert \geq mn.$

Or, $x$ et $y$ sont deux éléments de $U_{mn}$ donc $0\leq x \leq mn -1$ et $0\leq y \leq mn-1.$

Par suite, $1-mn\leq -y \leq 0$ et par somme avec $0\leq x\leq mn-1$ il vient $1-mn \leq x-y \leq mn-1.$

Cette double inégalité fournit $\vert x-y \vert \leq mn-1.$ Or, $mn\leq \vert x-y\vert$ du coup $mn\leq mn-1$ ce qui est une contradiction.

Ainsi, $k=0$ et $x-y=0$ et $x=y.$ L’injectivité de la fonction $f$ est ainsi démontrée.

Démontrez la surjectivité de cette application

Soit $(u,v)$ un couple de l’ensemble $U_m\times U_n.$

Grâce au théorème chinois, dont une preuve se trouve dans un autre article, il existe un entier $x$ tel que :

\left\{\begin{align*} x&\equiv u\text{ modulo }m\\ x&\equiv v\text{ modulo }n. \end{align*} \right.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 309.

Sans utiliser le symbole de la congruence, cela signifie qu’il existe un entier $r$ et un entier $s$ tels que :

\left\{\begin{align*} x = u +rm\\ x = v+ sn. \end{align*} \right.

A priori, rien ne garantit que $x$ soit positif ni qu’il soit compris entre $0$ et $mn-1.$

Vous notez $y$ le reste de la division euclidienne de l’entier relatif $x$ par le produit $mn.$

Il existe un entier $q$ tel que $x = qmn + y$ et l’inégalité $0\leq y \leq mn-1$ est vérifiée.

D’une part :

\begin{align*} y &= x-qmn\\ &=u+rm-qmn\\ &=(r-qn)m+u. \end{align*}

Comme $r-qn$ est un entier et que $u$ est compris entre $0$ et $m-1\comma$ l’entier $u$ est le reste de la division de $y$ par $m\comma$ donc $u = (y\mod m).$

D’autre part :

\begin{align*} y &= x-qmn\\ &=v+sn-qmn\\ &=(s-qm)n+v. \end{align*}

Comme $s-qm$ est un entier et que $v$ est compris entre $0$ et $n-1\comma$ l’entier $v$ est le reste de la division de $y$ par $n\comma$ donc $v = (y\mod n).$

Notez maintenant $d$ le plus grand diviseur commun des entiers $y$ et $m.$

Comme $d\mid m$ et $d\mid y\comma$ l’entier $d$ divise $y-(r-qn)m\comma$ c’est-à-dire $u.$ Ainsi $d$ est un diviseur commun à $u$ et à $m.$ Comme $u\in U_m\comma$ vous avez $\pgcd(u,m)=1\comma$ donc $d = 1$ et par suite $\pgcd(y,m)=1.$

Notez maintenant $\delta$ le plus grand diviseur commun des entiers $y$ et $n.$

Comme $\delta\mid n$ et $\delta\mid y\comma$ l’entier $\delta$ divise $y-(s-qm)n\comma$ c’est-à-dire $v.$ Ainsi $\delta$ est un diviseur commun à $v$ et à $n.$ Comme $v\in U_n\comma$ vous avez $\pgcd(v,n)=1\comma$ donc $\delta = 1$ et par suite $\pgcd(y,n)=1.$

Il s’agit de comprendre maintenant pourquoi $\pgcd(y,mn)=1.$ Si tel n’est pas le cas, $\pgcd(y,mn)\geq 2$ et il existe un nombre premier $p$ tel que $p$ divise $\pgcd(y,mn).$ Comme $\pgcd(y,mn)$ divise $mn$ vous déduisez que $p$ divise $mn.$

Par le lemme d’Euclide, soit $p$ divise $m\comma$ soit $p$ divise $n.$
Supposez que $p$ divise $m.$ Alors, $p$ divisant $\pgcd(y,mn)$ qui divise $y\comma$ vous déduisez $p\mid y.$ Du coup $p$ est un diviseur commun à $y$ et à $m.$ Comme $\pgcd(y,m)=1$ vous déduisez $p\leq 1$ ce qui est impossible, puisque $p$ en tant que nombre premier est supérieur ou égal à $2.$
Supposez que $p$ divise $n.$ Alors le raisonnement est similaire. En effet, vous trouvez $p\mid y$ et $p\mid n.$ Comme $\pgcd(y,n)=1$ cela entraîne $p\leq 1$ ce qui est impossible.

Du coup $\pgcd(y,mn)=1$ avec $0\leq y \leq mn-1.$ Donc $y$ est un élément de $U_{mn}.$

Il vient alors :

\begin{align*} f(y) &= ((y\mod m), (y\mod n))\\ &= (u,v). \end{align*}

La surjectivité de $f$ est ainsi démontrée.

Concluez

L’application $f$ est une bijection de $U_{mn}$ dans $U_m\times U_n.$

Les ensembles de départ et d’arrivée de $f$ ont donc le même nombre d’éléments. Comme l’ensemble produit $U_m\times U_n$ possède $\varphi(m)\times\varphi(n)$ éléments, vous obtenez le résultat :

\varphi(mn)=\varphi(m)\times \varphi(n).