Accéder à mon compte > Accéder à ma feuille d'exercices >

Indicateur d'Euler - Bibm@th.net

Exercice 1

- Indicateur d'Euler [Signaler une erreur] [Ajouter à ma feuille d'exos]

Pour $n\geq 1$ un entier, on définit l'indicateur d'Euler de $n$ par : $$\phi(n)=\textrm{card}\{1\leq k\leq n;\ k\textrm{ est premier avec }n\}.$$

Calculer $\phi(p)$ lorsque $p$ est un nombre premier.
Calculer $\phi(p^\alpha)$, où $p$ est premier et $\alpha\geq 1$.
Que signifie $\phi(n)$ pour l'anneau $\mathbb Z/n\mathbb Z$?
En déduire que si $n\wedge m=1$, alors $\phi(nm)=\phi(n)\phi(m)$.
Déduire des questions précédentes une formule pour calculer $\phi(n)$ pour tout entier $n$.
1. Soit $d$ un diviseur de $n$. On pose $$A_d=\left\{1\leq k\leq n;\ k\wedge n=d\right\}.$$ Quel est le cardinal de $A_d$?
2. En déduire que $n=\sum_{d|n}\phi(d).$

Indication

Corrigé

Tous les nombres compris entre $1$ et $p$, sauf $p$ lui-même, sont premiers avec $p$ puisque $p$ est premier. Donc $\phi(p)=p-1$.
Le pgcd de $k$ et de $p^\alpha$ n'est pas égal à 1 si et seulement si $k$ est un multiple de $p$. Il suffit donc de compter le nombre de multiples de $p$ qui sont inférieurs ou égaux à $p^\alpha$ et de retrancher ce nombre à $p^\alpha$. Un tel nombre s'écrit $p\times l$ avec $p\times l\leq p^{\alpha}$, soit $l\leq p^{\alpha-1}$. On obtient donc $$\phi(p^\alpha)=p^\alpha-p^{\alpha-1}.$$
$k$ est premier avec $n$ si et seulement si sa classe est inversible dans l'anneau $\mathbb Z/n\mathbb Z$. Ainsi, $\phi(n)$ désigne le nombre d'éléments inversibles de $\mathbb Z/n\mathbb Z$.
D'après le théorème chinois, les anneaux $\mathbb Z/nm\mathbb Z$ et $\mathbb Z/n\mathbb Z\times \mathbb Z/m\mathbb Z$ sont isomorphes. Le groupe de leurs éléments inversibles sont également isomorphes. D'autre part, pour deux anneaux $A$ et $B$, il est facile de prouver que $(A\times B)^*=A^*\times B^*$. Ainsi, $$\left(\mathbb Z/nm\mathbb Z\right)^*\textrm{ et }\left(\mathbb Z/n\mathbb Z\right)^*\times\left(\mathbb Z/m\mathbb Z\right)^*$$ sont isomorphes et ont donc le même nombre d'éléments. En calculant ce nombre d'éléments, on trouve : $$\phi(nm)=\phi(n)\phi(m).$$
On décompose $n$ en produits de facteurs premiers $n=p_1^{\alpha_1}\dots p_r^{\alpha_r}$. On trouve \begin{eqnarray*} \phi(n)&=&\phi\left(p_1^{\alpha_1}\right)\dots \phi\left(p_r^{\alpha_r}\right)\\ &=&\left(p_1^{\alpha_1}-p_1^{\alpha_1-1}\right)\times\dots\times\left(p_r^{\alpha_r}-p_r^{\alpha_r-1}\right)\\ &=&n\left(1-\frac1{p_1}\right)\dots\left(1-\frac1{p_r}\right). \end{eqnarray*}
1. Soit $k\in A_d$. Alors $k$ s'écrit $d\times l$, avec $l\wedge \frac nd=1$ et $1\leq ld\leq n$ ce qui entraîne $1\leq l\leq\frac nd$ (remarquons que $\frac nd$ est entier). Réciproquement, tout entier $k$ s'écrivant $d\times l$ avec $1\leq l\leq \frac nd$ et $l\wedge \frac nd=1$ est élément de $A_d$. On en déduit que $$\textrm{card}(A_d)=\phi\left(\frac nd\right).$$
2. Il est clair que les ensembles $A_d$, pour $d|n$, forment une partition de $\{1,\dots,n\}$. Ainsi, on a $$n=\sum_{d|n}\textrm{card}(A_d)=\sum_{d|n}\phi\left(\frac nd\right)=\sum_{d|n}\phi(d).$$ Pour obtenir la dernière inégalité, on a effectué le changement de variables $d'=n/d$.