Qu'est-ce que l'indicatrice d'Euler ?
L'indicatrice d'Euler, notée \(\varphi(n)\), compte le nombre d'entiers positifs compris entre 1 et n qui n'ont aucun diviseur commun avec n autre que 1 — autrement dit, les entiers premiers avec n. Par exemple, \(\varphi(9) = 6\), car 1, 2, 4, 5, 7 et 8 sont tous premiers avec 9. Cette fonction est fondamentale en théorie des nombres et intervient partout en cryptographie, notamment dans l'algorithme RSA, où \(\varphi(n)\) sert à déterminer l'inverse modulaire utilisé pour générer les clés.
Comment utiliser ce calculateur
Saisissez n'importe quel entier positif n, puis lancez le calcul. L'outil décompose n en ses facteurs premiers distincts et applique la formule du produit pour renvoyer \(\varphi(n)\) instantanément, accompagné de la liste des nombres premiers distincts trouvés. Il fonctionne aussi bien pour les petits nombres que pour de très grands, jusqu'à un milliard.
La formule expliquée
La méthode efficace pour calculer l'indicatrice repose sur la formule du produit :
$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$, le produit portant sur chaque nombre premier distinct p qui divise n.
Seuls les nombres premiers distincts comptent, et non leurs multiplicités. Chaque facteur \(\left(1 - \frac{1}{p}\right)\) retranche la proportion des entiers divisibles par ce nombre premier.
Exemple détaillé
Prenons \(n = 36\). Sa décomposition en facteurs premiers est \(2^2 \times 3^2\), donc les nombres premiers distincts sont 2 et 3. On obtient alors :
$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}.$$
Ainsi, exactement 12 entiers compris entre 1 et 36 sont premiers avec 36.
Questions fréquentes
Que vaut \(\varphi(1)\) ? Par convention, \(\varphi(1) = 1\), puisque 1 est premier avec lui-même.
Que vaut \(\varphi\) d'un nombre premier p ? Pour tout nombre premier p, \(\varphi(p) = p - 1\), car tous les entiers de 1 à \(p-1\) sont premiers avec p.
L'indicatrice est-elle multiplicative ? Oui. Si \(\gcd(a, b) = 1\), alors \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\) : c'est précisément ce qui justifie le produit sur les nombres premiers distincts.
