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
- 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)
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.
