L’indicatrice d’Euler φ(n) compte combien d’entiers de 1 à n sont premiers avec n, c’est-à-dire sans facteur premier commun avec lui. C’est un outil de base de la théorie des nombres et le moteur du chiffrement RSA. Saisissez la décomposition en facteurs premiers de n (jusqu’à trois nombres premiers distincts avec leurs exposants) et le calculateur donne φ(n), la part des entiers premiers avec n et la formule produit.
Comment se fait le calcul
Pour n = p₁^a₁ × p₂^a₂ × p₃^a₃, avec des nombres premiers distincts :
- φ(n) = Π p^(a−1) × (p − 1) sur les facteurs premiers
- De façon équivalente φ(n) = n × Π (1 − 1/p)
- Part des entiers premiers avec n = φ(n) ÷ n
- Entiers avec un facteur commun = n − φ(n)
Un facteur d’exposant 0 est omis. Le calculateur ne vérifie pas que vos facteurs sont premiers.
Exemple
Prenons n = 2³ × 3² × 5 = 360. Les facteurs donnent (2² × 1) × (3 × 2) × (1 × 4) = 4 × 6 × 4 = 96. Donc φ(360) = 96 : il y a 96 entiers de 1 à 360 premiers avec 360, soit 26,67 % d’entre eux, et 264 ont un facteur commun avec lui. Le produit (1 − ½)(1 − ⅓)(1 − ⅕) vaut 0,2667.
Pourquoi c’est important
En RSA, un module n = p × q est le produit de deux grands nombres premiers, et φ(n) = (p − 1)(q − 1) sert à trouver la clé privée. Le théorème d’Euler utilise φ(n) pour calculer des puissances modulo n, et l’indicatrice donne aussi le nombre de générateurs d’un groupe cyclique et le nombre de fractions irréductibles de dénominateur n.
Bon à savoir
φ(n) est toujours pair pour n supérieur à 2. Pour une puissance d’un nombre premier, φ(pᵃ) = pᵃ − pᵃ⁻¹. Pour deux entiers premiers entre eux, φ(mn) = φ(m) × φ(n). Les facteurs saisis doivent être des nombres premiers distincts : un nombre composé ou un nombre premier répété donne un résultat faux. Cet outil est pédagogique.
En pratique
Décomposez d’abord n à la main ou avec un outil, saisissez chaque nombre premier avec son exposant, et vérifiez le résultat sur un petit exemple comme 12, où φ(12) = 4.
Outils associés
Le calculateur du PGCD et du PPCM relie deux entiers, celui de l’équation du second degré résout le degré deux, et celui de l’équation du troisième degré trouve les racines d’un polynôme de degré trois.