La Fonction d'Euler

Spécialité Mathématiques - Arithmétique et Théorie des Nombres

Introduction à la Fonction d'Euler

La fonction d'Euler, notée \(\phi(n)\), est une fonction importante en théorie des nombres. Elle compte le nombre d'entiers positifs inférieurs ou égaux à n qui sont premiers avec n (c'est-à-dire dont le PGCD avec n est 1).

Définition formelle

Pour tout entier positif n, la fonction d'Euler φ(n) est définie comme :

\[\phi(n) = |\{k \in \mathbb{N} : 1 \leq k \leq n \text{ et } \gcd(k,n) = 1\}|\]

où |.| désigne le cardinal de l'ensemble et gcd est le plus grand commun diviseur.

Propriétés importantes

1. Pour un nombre premier p

\[\phi(p) = p - 1\]

Car tous les nombres de 1 à p-1 sont premiers avec p.

2. Pour une puissance d'un nombre premier \(p^k\)

\[\phi(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p})\]

3. Multiplicativité

Si a et b sont premiers entre eux, alors :

\[\phi(ab) = \phi(a) \cdot \phi(b)\]

Calcul de φ(n) pour n quelconque

Pour calculer φ(n) pour n'importe quel n, on peut utiliser sa décomposition en facteurs premiers :

Si \(n = p_1^{k_1} \cdot p_2^{k_2} \cdot ... \cdot p_r^{k_r}\), alors : \[\phi(n) = n \cdot (1 - \frac{1}{p_1}) \cdot (1 - \frac{1}{p_2}) \cdot ... \cdot (1 - \frac{1}{p_r})\]

Exemples

Exemple 1: Calculons φ(12)

12 = 2² * 3

φ(12) = 12 * (1 - 1/2) * (1 - 1/3) = 12 * 1/2 * 2/3 = 4

En effet, les nombres premiers avec 12 inférieurs à 12 sont : 1, 5, 7, 11.

Exemple 2: Calculons φ(15)

15 = 3 * 5

φ(15) = 15 * (1 - 1/3) * (1 - 1/5) = 15 * 2/3 * 4/5 = 8

Les nombres premiers avec 15 inférieurs à 15 sont : 1, 2, 4, 7, 8, 11, 13, 14.

Applications de la fonction d'Euler

Exercices proposés

  1. Calculez φ(36)
  2. Trouvez tous les nombres n tels que φ(n) = 10
  3. Démontrez que si p et q sont deux nombres premiers distincts, alors φ(pq) = (p-1)(q-1)
  4. Calculez φ(1000)
Accéder aux exercices complets