Calcul de l’indicatrice d’Euler
Calculez instantanément la fonction indicatrice d’Euler φ(n), visualisez sa valeur sur un graphique, obtenez la décomposition en facteurs premiers et comprenez la méthode de calcul pas à pas.
Calculateur interactif
Résultat
Entrez une valeur puis cliquez sur Calculer φ(n).
Visualisation de φ(k)
Le graphique ci-dessous affiche l’évolution de l’indicatrice d’Euler de 1 à la borne choisie.
Guide expert du calcul de l’indicatrice d’Euler
L’indicatrice d’Euler, notée φ(n), est l’une des fonctions les plus importantes de la théorie des nombres. Elle mesure combien d’entiers positifs inférieurs ou égaux à n sont premiers avec n, c’est-à-dire combien ont un plus grand commun diviseur égal à 1 avec n. Cette idée paraît simple, mais elle est au coeur de nombreux résultats fondamentaux en arithmétique, en algèbre et même en cryptographie moderne.
Définition de l’indicatrice d’Euler
Pour un entier positif n, la fonction φ(n) compte le nombre d’entiers k vérifiant 1 ≤ k ≤ n et pgcd(k, n) = 1. On dit alors que k et n sont premiers entre eux. Par exemple, pour n = 10, les entiers 1, 3, 7 et 9 sont premiers avec 10. On obtient donc φ(10) = 4.
La force de cette fonction vient du fait qu’elle ne nécessite pas de tester tous les entiers un à un lorsque l’on connaît la décomposition de n en facteurs premiers. Si n = p1^a1 × p2^a2 × … × pr^ar, alors :
φ(n) = n × ∏(1 – 1/p), où le produit porte sur les facteurs premiers distincts de n.
Pourquoi cette fonction est-elle si importante ?
La fonction indicatrice d’Euler intervient dans plusieurs domaines :
- dans le calcul de congruences et l’arithmétique modulaire ;
- dans le théorème d’Euler, qui généralise le petit théorème de Fermat ;
- dans les groupes multiplicatifs modulo n ;
- dans les méthodes de chiffrement comme RSA ;
- dans l’étude statistique des entiers premiers entre eux.
Le théorème d’Euler affirme que si a et n sont premiers entre eux, alors a^φ(n) ≡ 1 mod n. Cette relation est fondamentale en cryptographie, car elle permet de construire des mécanismes d’exponentiation modulaire inversible. Dans RSA, la connaissance de φ(n) est directement liée à la structure de la clé privée lorsque n est le produit de deux grands nombres premiers.
Comment calculer φ(n) pas à pas
1. Décomposer n en facteurs premiers
La première étape consiste à écrire n sous la forme d’un produit de puissances de nombres premiers. Par exemple :
- 12 = 2² × 3
- 45 = 3² × 5
- 100 = 2² × 5²
2. Ne garder que les facteurs premiers distincts
Pour appliquer la formule de l’indicatrice d’Euler, on n’a pas besoin des exposants dans le produit multiplicatif final. On conserve seulement la liste des premiers distincts. Pour 100, les facteurs premiers distincts sont 2 et 5.
3. Appliquer la formule multiplicative
On utilise alors :
- partir de n ;
- multiplier successivement par (1 – 1/p) pour chaque facteur premier distinct p ;
- simplifier le résultat.
Exemple avec 45 :
- 45 = 3² × 5
- φ(45) = 45 × (1 – 1/3) × (1 – 1/5)
- φ(45) = 45 × 2/3 × 4/5 = 24
4. Vérifier par comptage direct pour les petites valeurs
Pour des petits entiers, on peut confirmer le résultat en listant les nombres premiers avec n. Pour 9, les entiers 1, 2, 4, 5, 7, 8 sont premiers avec 9, donc φ(9) = 6. La formule donne aussi 9 × (1 – 1/3) = 6.
Cas particuliers à connaître
Si n est premier
Si p est un nombre premier, alors tous les entiers de 1 à p – 1 sont premiers avec p. On obtient immédiatement :
φ(p) = p – 1.
Si n est une puissance d’un premier
Si n = p^k, alors :
φ(p^k) = p^k – p^(k-1) = p^k(1 – 1/p).
Exemple : φ(16) = 16 – 8 = 8.
Si n est le produit de deux premiers distincts
Si n = p × q avec p et q premiers distincts, alors :
φ(n) = (p – 1)(q – 1).
Par exemple, φ(35) = (5 – 1)(7 – 1) = 24.
Tableau comparatif de valeurs de φ(n)
Le tableau suivant présente des valeurs réelles de l’indicatrice d’Euler pour différents entiers usuels. Il est utile pour repérer les régularités et comprendre l’effet de la factorisation.
| n | Décomposition | φ(n) | Ratio φ(n)/n | Observation |
|---|---|---|---|---|
| 10 | 2 × 5 | 4 | 0,40 | Deux facteurs premiers distincts réduisent la proportion de nombres premiers avec n. |
| 12 | 2² × 3 | 4 | 0,33 | La présence de 2 et 3 fait baisser fortement le ratio. |
| 13 | Premier | 12 | 0,92 | Pour un nombre premier, presque tous les entiers inférieurs sont copremiers. |
| 24 | 2³ × 3 | 8 | 0,33 | Les puissances n’ajoutent pas de nouveaux facteurs distincts, mais n modifient pas le produit de base. |
| 36 | 2² × 3² | 12 | 0,33 | Le ratio dépend uniquement des premiers distincts 2 et 3. |
| 49 | 7² | 42 | 0,86 | Une puissance d’un grand premier conserve un ratio élevé. |
Interprétation statistique
Le ratio φ(n)/n peut être interprété comme la proportion d’entiers entre 1 et n qui sont premiers avec n. Plus n possède de petits facteurs premiers distincts, plus ce ratio tend à diminuer. À l’inverse, si n est premier ou puissance d’un grand nombre premier, la proportion reste élevée.
Ce comportement permet d’expliquer des contrastes marqués entre des nombres de taille similaire. Par exemple, 30 et 31 sont très proches, mais φ(30) = 8 tandis que φ(31) = 30. Le premier contient les facteurs 2, 3 et 5 ; le second est un nombre premier.
| Nombre | Facteurs premiers distincts | Valeur de φ(n) | Ratio | Lecture rapide |
|---|---|---|---|---|
| 30 | 2, 3, 5 | 8 | 0,27 | Très composite, peu d’entiers copremiers en proportion. |
| 31 | 31 | 30 | 0,97 | Nombre premier, presque tous les entiers sont admissibles. |
| 64 | 2 | 32 | 0,50 | Puissance de 2 : exactement la moitié des entiers sont impairs et donc copremiers. |
| 81 | 3 | 54 | 0,67 | Puissance de 3 : deux tiers des résidus sont copremiers. |
| 210 | 2, 3, 5, 7 | 48 | 0,23 | Quatre petits facteurs distincts font chuter la proportion. |
Relation avec le théorème d’Euler et la cryptographie
L’une des grandes applications de φ(n) est le théorème d’Euler : si a et n sont premiers entre eux, alors a^φ(n) ≡ 1 mod n. Ce résultat est central pour comprendre les inverses multiplicatifs, les cycles de puissances modulo n et les schémas d’exponentiation utilisés en sécurité numérique.
Dans RSA, on choisit souvent n = p × q avec p et q premiers. Alors φ(n) = (p – 1)(q – 1). La sécurité pratique du système vient du fait qu’il est difficile, pour de grands n, de retrouver p et q et donc de recalculer efficacement φ(n) sans factorisation. C’est pourquoi l’indicatrice d’Euler a une portée bien au-delà de la théorie pure.
Erreurs fréquentes dans le calcul de l’indicatrice d’Euler
- Confondre nombres inférieurs à n et inférieurs ou égaux à n : la définition standard compte les entiers de 1 à n, mais n lui-même n’est jamais premier avec n sauf pour n = 1.
- Utiliser tous les facteurs au lieu des facteurs distincts : dans le produit ∏(1 – 1/p), chaque premier distinct n’apparaît qu’une seule fois.
- Supposer que φ(ab) = φ(a)φ(b) sans condition : cette multiplicativité n’est vraie que si a et b sont premiers entre eux.
- Oublier le cas n = 1 : par convention, φ(1) = 1.
Exemples détaillés
Exemple 1 : calcul de φ(18)
On factorise : 18 = 2 × 3². Les facteurs premiers distincts sont 2 et 3. Donc :
φ(18) = 18 × (1 – 1/2) × (1 – 1/3) = 18 × 1/2 × 2/3 = 6.
Vérification par comptage : 1, 5, 7, 11, 13, 17 sont premiers avec 18.
Exemple 2 : calcul de φ(25)
25 = 5², donc :
φ(25) = 25 × (1 – 1/5) = 20.
Autrement dit, seuls les multiples de 5 ne sont pas premiers avec 25.
Exemple 3 : calcul de φ(72)
72 = 2³ × 3². Les facteurs distincts sont 2 et 3. Ainsi :
φ(72) = 72 × 1/2 × 2/3 = 24.
Ressources académiques et institutionnelles
Pour approfondir la théorie des nombres et les usages de φ(n), vous pouvez consulter des sources fiables :
- Présentation de la fonction indicatrice d’Euler pour une vue synthétique des propriétés fondamentales.
- Carnegie Mellon University (.edu) sur l’algorithme d’Euclide et l’arithmétique modulaire.
- NIST (.gov) pour le contexte institutionnel du chiffrement RSA.
- Harvard University (.edu) pour des notes avancées en théorie des nombres.
Conseils pratiques pour utiliser ce calculateur
- Entrez un entier positif n.
- Choisissez la borne du graphique pour comparer φ(k) pour plusieurs valeurs de k.
- Sélectionnez un affichage simple ou détaillé.
- Cliquez sur le bouton de calcul pour obtenir φ(n), les facteurs premiers et le ratio φ(n)/n.
- Analysez le graphique pour repérer les nombres premiers, les puissances de premiers et les entiers très composites.
Questions fréquentes
φ(1) vaut-il 0 ou 1 ?
Par convention, φ(1) = 1.
Pourquoi φ(p) = p – 1 si p est premier ?
Parce que tout entier de 1 à p – 1 est automatiquement premier avec p.
Pourquoi le ratio φ(n)/n baisse-t-il pour certains nombres ?
Parce que les petits facteurs premiers éliminent une plus grande proportion d’entiers candidats.
Conclusion
Le calcul de l’indicatrice d’Euler est à la fois élégant et extrêmement utile. Grâce à la décomposition en facteurs premiers, il devient possible de déterminer rapidement combien d’entiers sont premiers avec n sans les tester tous. Cette fonction éclaire la structure multiplicative des entiers, joue un rôle décisif dans les congruences et soutient des applications de premier plan en cryptographie. Le calculateur interactif ci-dessus vous permet non seulement de trouver φ(n), mais aussi de visualiser son comportement sur un intervalle et de mieux comprendre les mécanismes qui gouvernent cette fonction centrale de la théorie des nombres.