Indicatrice d'Euler

L'indicatrice d'Euler, notée avec la lettre grecque phi : \( \phi(n) \) ou \( \varphi(n) \) est le nombre représentant le nombre d'entiers inférieurs à \( n \) qui sont premiers avec \( n \)

Phi(n) (indicatrice euler) se calcule de plusieurs manières, la formule la plus connue est $$ \varphi(n) = n \prod_{p \mid n} \left( 1 - \frac{1}{p} \right) $$

où \( p \) est un facteur premier qui divise \( n \).

Pour calculer la valeur de l'indicateur d'Euler, réaliser la décomposition en facteurs premiers de \( n \). Soient \( p_i \) les \( m \) facteurs premiers distincts de \( n \). La formule devient :

$$ \varphi(n) = n \prod_{i=1}^m \left( 1 - \frac{1}{p_i} \right) $$

Exemple : Pour \( n = 6 \), seuls les nombres \( 1 \) et \( 5 \) sont premiers avec \( 6 \) donc \( \varphi(6) = 2 \). Ce que confirme la formule pour \( n = 6 = 2^1 \times 3^1 \) : $$ \varphi(6) = 6 (1-\frac{1}{2}) (1-\frac{1}{3}) = 2 $$

Si \( n \) est un nombre premier, alors \( \varphi(n) = n-1 \)

La fonction indicatrice d'Euler (phi) est utilisée en arithmétique modulaire. Elle est notamment utilisée dans le Théorème d'Euler :

Soit \( n \) est un entier supérieur à 1 et \( a \) un entier premier avec \( n \), alors $$ a^{\phi(n)} \equiv 1 \mod n $$

Exemple : \( n=7 \) , \( a=3 \) et \( \phi(7) = 6 \) alors \( 3^6 = 729 \equiv 1 \mod 7 \)

Ce théorème est d'ailleurs la base du chiffrement RSA.