Calculateur de l'indicatrice d'Euler

Calculateur de l'indicatrice d'Euler

En croissance AI Skill PRO

Entrez le calcul

Formule

φ(n)=n∏p|n(1−1p)\varphi\!\left(\text{n}\right) = \text{n} \prod_{p \mid \text{n}} \left(1 - \frac{1}{p}\right)
Statistiques d'utilisation

Publicité

Résultats

Indicatrice d'Euler φ(32)
16
entiers premiers avec 32 in [1, n]
Valeur de n 32
Facteurs premiers distincts 2

Signaler une erreur sur cette page

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.

Grille d'entiers de 1 à 12 avec ceux premiers avec 12 mis en évidence
L'indicatrice d'Euler compte les entiers jusqu'à n qui n'ont aucun facteur commun avec n.

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.

Publicité
Schéma décomposant n en facteurs premiers puis le multipliant par des termes (1 moins 1 sur p)
La formule du produit multiplie n par un facteur \(\left(1 - \frac{1}{p}\right)\) pour chaque diviseur premier distinct p.

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\).

  1. Partir de \(210\).
  2. Multiplier par \(1-\frac{1}{2} = \frac{1}{2}\) : \(210 \cdot \frac{1}{2} = 105\).
  3. Multiplier par \(1-\frac{1}{3} = \frac{2}{3}\) : \(105 \cdot \frac{2}{3} = 70\).
  4. Multiplier par \(1-\frac{1}{5} = \frac{4}{5}\) : \(70 \cdot \frac{4}{5} = 56\).
  5. 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\).

Publicité

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.

Dernière mise à jour:

Les plus populaires dans Mathématiques et statistiques

Voir toutes les calculatrices de Mathématiques et statistiques