Indicatrice d'Euler

L'indicateur 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 détermine de plusieurs manières. La formule de calcul la plus connue pour déterminer la valeur de l'indicateur d'Euler, utilise la décomposition en facteurs premiers de $ n $. Soient $ p_i $ les $ m $ facteurs premiers distincts diviseurs de $ n $ (de multiplicité $ k $). La formule (1) est :

$$ \varphi(n) = \prod_{i=1}^m (p_i-1) p_i^{k_i-1} \quad\quad (1) $$

Après simplification, une autre formulation (2) est :

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

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

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

La suite des valeurs de Phi(n) est 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, etc. ici (lien)

Le calcul de Euler phi(n) peut être codé avec un algorithme comme :
function phi(n) {
r = n;
for (i = 2; i*i <= n; i++) {
if (n % i == 0) {
r -= r / i;
while (n % i == 0) {
n /= i;
}
}
}
r -= r / n;
return r;
}