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.
Exemples travaillés supplémentaires
Exemple 1 : un nombre premier, φ(13)
13 est premier, donc son seul facteur premier est 13 lui-même :
\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12. Cela correspond à la règle abrégée pour les nombres premiers \(\varphi(p) = p-1\).
Exemple 2 : une puissance d'un nombre premier, φ(32)
Décomposition : \(32 = 2^5\). Le seul nombre premier distinct est 2.
\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16.
Forme équivalente pour une puissance d'un nombre premier : \(\varphi(p^k) = p^k - p^{k-1}\), donc \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\). Ce sont exactement les nombres impairs de 1 à 31.
Exemple 3 : trois nombres premiers distincts ou plus, φ(210)
Décomposition : \(210 = 2 \cdot 3 \cdot 5 \cdot 7\).
- Partir de \(210\).
- Multiplier par \(1-\frac{1}{2} = \frac{1}{2}\) : \(210 \cdot \frac{1}{2} = 105\).
- Multiplier par \(1-\frac{1}{3} = \frac{2}{3}\) : \(105 \cdot \frac{2}{3} = 70\).
- Multiplier par \(1-\frac{1}{5} = \frac{4}{5}\) : \(70 \cdot \frac{4}{5} = 56\).
- Multiplier par \(1-\frac{1}{7} = \frac{6}{7}\) : \(56 \cdot \frac{6}{7} = 48\).
Donc \(\varphi(210) = \)48. Notez que la règle du produit n'utilise chaque nombre premier distinct qu'une seule fois. Par exemple, \(60 = 2^2 \cdot 3 \cdot 5\) donne \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\).
Interpréter φ(n) et ses utilisations
- Lien avec la primalité : pour \(n \ge 2\), \(\varphi(n) = n-1\) si et seulement si \(n\) est premier. Tout nombre inférieur à un nombre premier lui est premier entre soi. Si \(n\) est composé, au moins un nombre qui lui est inférieur partage un facteur avec lui, donc \(\varphi(n) < n-1\).
- Groupe des unités : \(\varphi(n)\) est le nombre d'éléments du groupe des unités modulo \(n\), c'est-à-dire des résidus qui possèdent un inverse multiplicatif modulo \(n\). Pour \(n = 15\), ce sont 1, 2, 4, 7, 8, 11, 13, 14, soit 8 éléments.
- Théorème d'Euler : si \(\gcd(a, n) = 1\), alors \(a^{\varphi(n)} \equiv 1 \pmod{n}\). Exemple : \(a = 2\), \(n = 15\), \(\varphi(15) = \)8, et \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\). Le petit théorème de Fermat est le cas particulier où \(n = p\) est premier.
- RSA : lorsque \(n = pq\) avec \(p\) et \(q\) premiers distincts, \(\varphi(n) = (p-1)(q-1)\). Avec \(n = 15 = 3 \cdot 5\) : \(\varphi(15) = 2 \cdot 4 = 8\). L'exposant public \(e\) doit être premier avec \(\varphi(n)\), et l'exposant privé \(d\) vérifie \(ed \equiv 1 \pmod{\varphi(n)}\). Le RSA réel utilise des nombres premiers de plusieurs centaines de chiffres. Quiconque peut factoriser \(n\) peut calculer \(\varphi(n)\), ce qui explique pourquoi la sécurité repose sur la difficulté de la factorisation.
- Le rapport ne dépend que des nombres premiers distincts : \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\). Les exposants n'interviennent pas. Par exemple, 6 et 12 ont tous deux l'ensemble de nombres premiers {2, 3}, donc \(\varphi(6)/6 = 2/6 = 1/3\) et \(\varphi(12)/12 = 4/12 = 1/3\).
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.