Indicatrice d'Euler

L'indicatrice d'Euler (ou la fonction indicatrice d'Euler ou Euler totient en anglais), notée avec la lettre grecque phi : $ \varphi(n) $ ou $ \phi(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, la première étape nécessite de trouver la décomposition en facteurs premiers de $ n $. Soient $ p_i $ les $ m $ facteurs premiers distincts diviseurs de $ n $. La formule devient :

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

Résoudre $ \phi(x) = N $ nécessite un algorithme de recherche plus ou moins optimisé en se basant sur $ \phi(x) \geq \sqrt{\frac{x}{2}} $ qui va tester toutes les valeurs. Plus de détails ici (lien)

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^{\varphi(n)} \equiv 1 \mod n $$

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

L'indicatrice d'Euler est une fonction essentielle de l'arithmétique modulaire :

— Un nombre entier positif $ p $ est un nombre premier si et seulement si $ \varphi(p) = p - 1 $

— La valeur $ \varphi(n) $ est paire pour tout $ n > 2 $

— $ \varphi(ab) = \varphi(a) \varphi(b) \frac{d}{\varphi(d)} $ avec $ d $ le PGCD de $ a $ et $ b $

— Si $ a $ et $ b $ sont premiers entre eux, alors $ \varphi(a \times b) = \varphi(a) \times \varphi(b) $

— Si $ a $ divise $ b $ alors $ \varphi(a) \mid \varphi(b) $

— Si $ a $ est pair, $ \varphi(2a) = 2 \varphi(a) $

— Si $ a $ est impair, $ \varphi(2a) = \varphi(a) $