Aller au contenu
Omnikalc

Indicatrice d'Euler : combien d'entiers sont premiers avec n ?

Saisissez les facteurs premiers de n et leurs exposants pour obtenir l'indicatrice d'Euler φ(n), la part des entiers premiers avec n et la formule produit.

Mis à jour le
Vos paramètres

Valeur hors limites

Valeur hors limites

Valeur hors limites

Valeur hors limites

Valeur hors limites

Valeur hors limites

Résultats

Indicatrice d'Euler φ(n)

96

Le nombre n
360
Part des entiers de 1 à n premiers avec n
26,67 %
Entiers de 1 à n qui ont un facteur commun avec n
264
Produit des (1 − 1/p) sur les facteurs premiers
0,2667

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.

Questions fréquentes

Qu'est-ce que l'indicatrice d'Euler ?

φ(n) compte les entiers de 1 à n qui sont premiers avec n, c'est-à-dire sans facteur premier commun avec lui. Pour un nombre premier p, tous les entiers plus petits conviennent, donc φ(p) = p − 1. Pour n = 12, les entiers 1, 5, 7 et 11 conviennent, donc φ(12) = 4.

Comment la calculer à partir des facteurs premiers ?

Si n = p₁^a₁ × p₂^a₂ × …, alors φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …, ce qui revient au produit des p^(a−1)(p−1) sur les facteurs premiers. Il faut d'abord la décomposition de n en facteurs premiers.

À quoi sert-elle ?

L'indicatrice est au cœur du chiffrement RSA, où les clés publique et privée sont liées par φ(n) = (p − 1)(q − 1) pour deux nombres premiers, et du théorème d'Euler, qui dit que a^φ(n) ≡ 1 (mod n) quand a et n sont premiers entre eux.

Le calculateur vérifie-t-il que mes facteurs sont premiers ?

Non. Vous saisissez vous-même les facteurs premiers, et le résultat n'est valable que s'ils sont bien premiers et distincts. Décomposez d'abord le nombre avec un outil de factorisation.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.