Dernière mise à jour : 2026-07-13

Définition

L'indicatrice d'Euler $\varphi(n)$ compte combien d'entiers de $1$ à $n$ sont premiers avec $n$, c'est-à-dire n'ayant aucun facteur commun avec $n$ autre que $1$. Deux entiers sont premiers entre eux lorsque leur plus grand commun diviseur vaut $1$.

Par exemple, $\varphi(9) = 6$ : parmi $1, 2, \dots, 9$, les valeurs $1, 2, 4, 5, 7, 8$ sont premières avec $9$, tandis que $3, 6, 9$ ne le sont pas.

La fonction porte le nom de Leonhard Euler, qui l'a introduite en 1763. On la note aussi $\phi(n)$ et on l'appelle fonction phi.

La formule du produit

Il est inutile de tester chaque entier jusqu'à $n$. Une fois $n$ décomposé en ses facteurs premiers distincts, l'indicatrice se déduit directement :

$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

Le produit porte sur les nombres premiers distincts divisant $n$ : les exposants n'apparaissent pas. Chaque premier $p$ retire la fraction $1/p$ des nombres (ceux divisibles par $p$), et comme les premiers agissent indépendamment, les fractions se multiplient.

Exemple résolu — n = 36. La décomposition est $36 = 2^2 \cdot 3^2$, donc les premiers distincts sont $2$ et $3$ :

$\varphi(36) = 36\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$

Les douze entiers premiers avec $36$ sont $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35$.

Nombres premiers et puissances de premiers

Deux cas fondamentaux rendent la formule facile à comprendre :

• Premier $p$ : tout entier de $1$ à $p - 1$ est premier avec $p$, donc $\varphi(p) = p - 1$. Par exemple $\varphi(7) = 6$.
• Puissance de premier $p^k$ : les seuls entiers non premiers avec $p^k$ sont les multiples de $p$, au nombre de $p^{k-1}$. D'où

$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$

Ainsi $\varphi(8) = \varphi(2^3) = 2^2(2 - 1) = 4$ et $\varphi(27) = \varphi(3^3) = 3^2(3 - 1) = 18$.

Multiplicativité

L'indicatrice est multiplicative : dès que $m$ et $n$ sont premiers entre eux,

$\varphi(mn) = \varphi(m)\,\varphi(n)$

C'est pourquoi la formule du produit fonctionne : on écrit $n$ comme produit de puissances de premiers, on applique $\varphi(p^k) = p^{k-1}(p-1)$ à chacune, puis on multiplie. Par exemple, $36 = 4 \cdot 9$ avec $\gcd(4, 9) = 1$, donc $\varphi(36) = \varphi(4)\,\varphi(9) = 2 \cdot 6 = 12$.

Attention à la condition de coprimalité : $\varphi(mn) = \varphi(m)\varphi(n)$ peut être fausse lorsque $m$ et $n$ partagent un facteur. Ainsi $\varphi(2 \cdot 2) = \varphi(4) = 2$, et non $\varphi(2)\varphi(2) = 1$.

Le théorème d'Euler

L'indicatrice régit l'exponentiation modulaire. Le théorème d'Euler énonce que si $\gcd(a, n) = 1$, alors

$a^{\varphi(n)} \equiv 1 \pmod{n}$

Cela généralise le petit théorème de Fermat ($a^{p-1} \equiv 1 \pmod p$ pour un premier $p$), qui n'est autre que le cas particulier $n = p$, où $\varphi(p) = p - 1$.

Exemple. Prenons $a = 3$, $n = 10$. Ici $\varphi(10) = 4$, donc $3^4 = 81 \equiv 1 \pmod{10}$, et en effet $81$ se termine par $1$. Le théorème permet de réduire d'énormes exposants modulo $\varphi(n)$ avant le calcul.

Application à RSA

La cryptographie à clé publique RSA se construit directement sur l'indicatrice. Un module est formé à partir de deux grands nombres premiers, $n = p \cdot q$, ce qui donne

$\varphi(n) = (p - 1)(q - 1)$

L'exposant public $e$ et l'exposant privé $d$ sont choisis pour que $e \cdot d \equiv 1 \pmod{\varphi(n)}$. Le théorème d'Euler garantit alors que déchiffrer inverse chiffrer : $(m^e)^d \equiv m \pmod n$.

La sécurité repose sur un écart : n'importe qui peut publier $n$, mais calculer $\varphi(n) = (p-1)(q-1)$ exige de connaître $p$ et $q$. Les retrouver à partir de $n$ seul revient à factoriser un grand semi-premier, ce que l'on croit impossible en pratique pour des premiers assez grands. En fait, connaître $\varphi(n)$ équivaut à factoriser $n$.

Exemples résolus

$n$	Décomposition	Forme produit	$\varphi(n)$
$10$	$2 \cdot 5$	$10\,(1 - \tfrac12)(1 - \tfrac15)$	$4$
$12$	$2^2 \cdot 3$	$12\,(1 - \tfrac12)(1 - \tfrac13)$	$4$
$36$	$2^2 \cdot 3^2$	$36\,(1 - \tfrac12)(1 - \tfrac13)$	$12$
$100$	$2^2 \cdot 5^2$	$100\,(1 - \tfrac12)(1 - \tfrac15)$	$40$
$101$	$101$ (premier)	$101\,(1 - \tfrac{1}{101})$	$100$

Cas particuliers

• $n = 1$ : par convention $\varphi(1) = 1$. Le seul entier de l'intervalle, $1$, est premier avec lui-même.
• $n$ premier : $\varphi(n) = n - 1$, le maximum pour cette taille ; les premiers ont le plus de restes qui leur sont premiers.
• $n$ pair : le facteur $(1 - \tfrac12)$ retire au moins la moitié des entiers, donc $\varphi(n) \le n/2$.
• Somme sur les diviseurs : les indicatrices de tous les diviseurs de $n$ ont pour somme $n$ : $\sum_{d \mid n} \varphi(d) = n$. Pour $n = 12$ : $\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$.

Aide-mémoire

Notion	Formule
Définition	$\varphi(n) = \#\{\, k : 1 \le k \le n,\ \gcd(k, n) = 1 \,\}$
Formule du produit	$\varphi(n) = n \prod_{p \mid n} (1 - 1/p)$
Nombre premier	$\varphi(p) = p - 1$
Puissance de premier	$\varphi(p^k) = p^{k-1}(p - 1)$
Multiplicative	$\varphi(mn) = \varphi(m)\varphi(n)$ si $\gcd(m, n) = 1$
Théorème d'Euler	$a^{\varphi(n)} \equiv 1 \pmod n$ si $\gcd(a, n) = 1$
Somme des diviseurs	$\sum_{d \mid n} \varphi(d) = n$

Questions fréquentes (FAQ)

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

L'indicatrice d'Euler φ(n) compte les entiers positifs jusqu'à n qui sont premiers avec n, c'est-à-dire sans facteur commun avec n autre que 1. Par exemple, φ(9) = 6, car 1, 2, 4, 5, 7 et 8 sont premiers avec 9, tandis que 3, 6 et 9 ne le sont pas. Par convention, φ(1) = 1.

Comment calcule-t-on φ(n) ?

Décomposez n en ses facteurs premiers distincts p₁, p₂, …, pₖ, puis appliquez φ(n) = n · ∏(1 − 1/p) sur ces facteurs premiers. Pour n = 36 = 2² · 3², φ(36) = 36 · (1 − 1/2) · (1 − 1/3) = 36 · 1/2 · 2/3 = 12. Seuls les facteurs premiers distincts comptent, pas leurs exposants.

Quelle est l'indicatrice d'un nombre premier ?

Pour un nombre premier p, tout entier de 1 à p − 1 est premier avec p, donc φ(p) = p − 1. Pour une puissance de premier pᵏ, la formule donne φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ⁻¹(p − 1). Par exemple, φ(7) = 6 et φ(8) = φ(2³) = 8 − 4 = 4.

Pourquoi l'indicatrice est-elle importante dans RSA et le théorème d'Euler ?

Le théorème d'Euler énonce que si pgcd(a, n) = 1, alors a^φ(n) ≡ 1 (mod n), une généralisation du petit théorème de Fermat. RSA en dépend : pour un module n = p·q formé de deux nombres premiers, φ(n) = (p − 1)(q − 1), et les exposants public et privé sont choisis pour que e·d ≡ 1 (mod φ(n)). Connaître φ(n) revient à factoriser n, et c'est ce qui rend RSA sûr.