Dans cet article, les notions d’anneaux et d’ensemble-quotient ne seront pas abordées. L’approche choisie consiste à démontrer le résultat 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, \mathrm{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 $\mathrm{PGCD}(m,n)=1$, alors :
\varphi(mn)=\varphi(m)\varphi(n).
Dans toute la suite de cet article, vous fixez deux entiers $m$ et $n$ non nuls fixés, tels que $\mathrm{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 $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 = \mathrm{PGCD}(r_m,m).$ Comme $d$ divise $m$, $d$ divise le produit $q_m m.$ Comme $d$ divise aussi $r_m$, 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$, c’est un diviseur commun à $x$ et à $mn.$ Or, $x\in U_{mn}$ donc $ \mathrm{PGCD}(x,mn) = 1.$ Il en résulte que $d=1.$
Il est ainsi démontré que $\mathrm{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}$ 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$, puis celle de $y$ par $m$, vous constatez qu’il existe un couple $(q_n,q_m)$ d’entiers tel que :
x = q_x m+(x\mod m)\\ y = q_y m + (y\mod m).
Comme $(x\mod m) = (y\mod m)$ 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$, 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 $\mathrm{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.$
Vous allez supposer que $k$ n’est pas 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 le contenu rédigé dans l'article 309, 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.Sans utiliser le symbôle 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, on n’est pas sûr que $x$ soit compris entre $0$ et $mn-1.$
Vous allez considérer $y = x\mod mn$, le reste de la division de $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$, l’entier $u$ est de reste de la division de $y$ par $m$, 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$, l’entier $v$ est de reste de la division de $y$ par $n$, donc $v = (y\mod n).$
Notez maintenant $d$ le plus grand diviseur commun des entiers $y$ et $m.$
Comme $d\mid m$ il vient $d\mid qmn.$ Or, $x = y+qmn$ donc $d\mid x.$ Comme $\mathrm{PGCD}(x,m)=1$ et que $d$ est un diviseur commun à $x$ et à $m$, vous déduisez $d = 1$ et par suite $\mathrm{PGCD}(y,m)=1.$
Notez maintenant $f$ le plus grand diviseur commun des entiers $y$ et $n.$
Comme $f\mid n$ il vient $f\mid qmn.$ Or, $x = y+qmn$ donc $f\mid x.$ Comme $\mathrm{PGCD}(x,m)=1$ et que $f$ est un diviseur commun à $x$ et à $m$, vous déduisez $f = 1$ et par suite $\mathrm{PGCD}(y,n)=1.$
Il s’agit de comprendre maintenant pourquoi $\mathrm{PGCD}(y,mn)=1.$ Si tel n’est pas le cas, $\mathrm{PGCD}(y,mn)\geq 2$ et il existe un nombre premier $p$ tel que $p$ divise $\mathrm{PGCD}(y,mn).$ Comme $\mathrm{PGCD}(y,mn)$ divise $mn$ vous déduisez que $p$ divise $mn.$
Par le lemme d’Euclide, soit $p$ divise $m$, soit $p$ divise $n.$
Supposez que $p$ divise $m$ alors $p$ divisant $\mathrm{PGCD}(y,mn)$ qui divise $y$, vous déduisez $p\mid y.$ Du coup $p$ est un diviseur commun à $y$ et à $m.$ Comme $\mathrm{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 $\mathrm{PGCD}(y,n)=1$ cela entraîne $p\leq 1$ ce qui est impossible.
Du coup $\mathrm{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, ce qui fournit le résultat :
\varphi(mn)=\varphi(m)\times \varphi(n).
Partagez !
Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !