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$ 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)$ qui est le nombre d’éléments de l’ensemble $A$ défini par :
A = \{m\in\llbracket 1, n\rrbracket, \mathrm{PGCD}(m, n)=1\}.Notation $\#$
Pour tout ensemble $E$, 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 le nombre d’éléments de $A.$ Vous allez donc dénombrer à la place le complémentaire de $A.$ Vous obtenez donc :
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$, 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 il $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,\exist 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é aussi 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< 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< \cdots < 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<\cdots < 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< \cdots < i_u$ les nombres premiers $p_{i_1}, \cdots, 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}.$ $x$ est un entier 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} yComme $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,\cdots, 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,\cdots, 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$ le nombre $\prod_{i\in{i_1,\cdots, 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\}.Cette écriture montre que le nombre d’éléments de l’ensemble $B_{i_1}\cap\cdots\cap B_{i_u}$ est égal à :
\boxed{\#(B_{i_1}\cap\cdots\cap B_{i_u}) = \frac{n}{p_{i_1}\cdots p_{i_u}}.}A ce stade il a été démontré que :
\begin{align*}
n-\varphi(n) &=\sum_{u=1}^k (-1)^{u+1}\sum_{\substack{1\leq i_1\leq k\\ \dots\\ 1\leq i_u\leq k\\i_1< \cdots < 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< \cdots < 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< \cdots < 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< \cdots < 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< \cdots < 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< \cdots < 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 à :
\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< \cdots < i_u}} \frac{1}{p_{i_1}\cdots p_{i_u}}\right).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 qu’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_k$ tels que :
r = \prod_{i=1}^{\kappa}\xi_i^{\alpha_i}.Vous décomposez $s$ en produit de nombres premiers. Il qu’il existe un entier naturel non nul $\lambda$ ainsi que des entiers naturels non nuls $\beta, \dots, \beta{\lambda}$ et des nombres premiers $\zeta_1\dots, \zeta_{\lambda}$ tels que :
s = \prod_{j=1}^{\lambda}\zeta_j^{\beta}.Comme $r$ et $s$ sont premiers entre eux, 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}\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_{i=j}^{\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*}Et vous concluez : la fonction d’Euler $\varphi$ est multiplicative :
\boxed{\forall (r,s)\in\N^2, \left\{\begin{align*} &r\geq 2\\&s\geq 2\\&PGCD(r,s)=1\end{align*}\right. \implies\varphi(rs)=\varphi(r)\varphi(s).}Partagez maintenant !
Aidez vos amis à découvrir cet article et à mieux comprendre le sujet.
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 !