L’indicatrice d’Euler est une fonction sur les entiers, qui a son utilité en arithmétique et en théorie des groupes et anneaux pour démontrer certains résultats. Voir même en analyse !
Prérequis
- Le théorème des nombres premiers
- Anneau Z/nZ
- Le théorème des restes chinois
Définition de l’indicatrice d’Euler
La fonction indicatrice d’Euler, notée \varphi est définie sur \mathbb{N}^* par
\varphi(n) =\text{card}\left( \left\{ m \in \{1, \ldots, n \} | m \wedge n = 1 \right\}\right)Théorème d’Euler
C’est une généralisation du petit théorème de Fermat. Soit n \in \mathbb{N}. Soit k \in \mathbb{Z} tel que k \wedge n = 1. On a le résultat suivant :
k^{\varphi(n)} \equiv 1 [n]Ce théorème est à la base du chiffrement RSA
Des propriétés importantes
- Si n et m sont premiers entre eux alors \varphi(nm) = \varphi(n) \varphi(m). Cette propriété nous provient du théorème des restes chinois.
- Généralisation : Soit d = n \wedge m . On a \varphi(n.m) = \varphi(a) \varphi(b) \dfrac{d}{\varphi(d)}
- On a la relation suivante : n = \displaystyle \sum_{n |d} \varphi(n)
- Si d | a alors \varphi(d) | \varphi(a)
Démontrons la formule n = \displaystyle \sum_{n |d} \varphi(n) .
Lemme : Si d|n, le groupe (\mathbb{Z} / n\mathbb{Z},+) possède exactement \varphi(d) éléments d’ordre d .
Un élément d’ordre d de \mathbb{Z} / n\mathbb{Z} est générateur d’un sous-groupe à d éléments donc générateur de \langle n / d \rangle . Inversement, tout générateur de \langle n/d \rangle est élément d’ordre d de \mathbb{Z} / n\mathbb{Z}. Or, \langle n/d \rangle est cyclique d’ordre d donc isomorphe à \mathbb{Z} / d \mathbb{Z} et possède ainsi \varphi(d) générateurs. On peut alors affirmer que \mathbb{Z} / n\mathbb{Z} possède exactement \varphi(d) éléments d’ordre d.
Le lemme est montré ! Passons à la démonstration de la formule !
L’ordre d’un élément de \mathbb{Z} / n\mathbb{Z} divise n d’après le théorème de Lagrange. D’après le lemme, on a \varphi(d) diviseurs d’ordre d. En parcourant tous les ordres, on peut donc conclure
n = \sum_{d=1}^n \#\{ x \in \Z/n\Z, o(x) = d\}= \sum_{d |n } \varphi(d)où o (x) est l’ordre de x.
Calcul de l’indicatrice d’Euler
Pour un nombre premier
Soit p un nombre premier. Si 1\leq m < p alors m est nécessairement premier avec p. On a donc, dans ce cas particulier, \varphi(p) = p - 1
Pour une puissance d’un nombre premier
Soit \alpha \in \mathbb{N}^* . On va donc considérer n = p^{\alpha}. Pour cela, on remarque qu’un nombre est premier avec n si et seulement si il n’est pas un multiple de p. Les multiples de p sont p, 2p, \ldots, p^{\alpha} - p, p . On en a donc p^{\alpha-1} . Ainsi, en prenant le complémentaire, on obtient
\varphi(p^{\alpha}) = p^{\alpha}-p^{\alpha-1} = p^{\alpha - 1}(p-1) Dans le cas général
Grâce au théorème des nombres premiers, on peut écrire n sous la forme n = \displaystyle \prod_{i=1}^r p_i^{\alpha_i} .
En utilisant r-1 fois la propriété sur le produit, on obtient que \varphi(n) = \displaystyle \prod_{i=1}^r \varphi(p_i^{\alpha_i}) = \prod_{i=1}^r \left(p_i^{\alpha_i} - p_i^{\alpha_i - 1}\right).
En transformant l’expression, on obtient \varphi(n) = \displaystyle \prod_{i=1}^r p_i^{\alpha_i}\left( 1 -\dfrac{1}{p_i}\right) = \prod_{i=1}^r p_i^{\alpha_i} \prod_{i=1}^r \left( 1 -\dfrac{1}{p_i}\right) = n \prod_{i=1}^r \left( 1 -\dfrac{1}{p_i}\right)
C’est cette forme là qui est la plus utilisée.
