Cours : Indicatrice d’Euler

Découvrez l’indicatrice d’Euler, une fonction qui est utile en arithmétique et en théorie des groupes, corps et anneaux
Euler

L’indicatrice d’Euler est une fonction sur les entiers, qui a son utilité en arithmétique et en théorie des groupes et anneaux pour démontrer certains résultats. Voir même en analyse !

Prérequis

Définition de l’indicatrice d’Euler

La fonction indicatrice d’Euler, notée \varphi est définie sur \mathbb{N}^* par 

\varphi(n) =\text{card}\left( \left\{ m \in \{1, \ldots, n \} | m \wedge n = 1 \right\}\right)

Théorème d’Euler

C’est une généralisation du petit théorème de Fermat. Soit n \in \mathbb{N}. Soit k \in \mathbb{Z} tel que k \wedge n =  1. On a le résultat suivant : 

k^{\varphi(n)} \equiv 1 [n]

Ce théorème est à la base du chiffrement RSA

Des propriétés importantes

  • Si n et m sont premiers entre eux alors \varphi(nm) = \varphi(n) \varphi(m). Cette propriété nous provient du théorème des restes chinois. 
  • Généralisation : Soit d = n \wedge m . On a \varphi(n.m) = \varphi(a) \varphi(b) \dfrac{d}{\varphi(d)}
  • On a la relation suivante : n = \displaystyle \sum_{n |d} \varphi(n)
  • Si d | a alors \varphi(d) | \varphi(a)

Calcul de l’indicatrice d’Euler

Pour un nombre premier

Soit p un nombre premier. Si 1\leq m < p alors m est nécessairement premier avec p. On a donc, dans ce cas particulier, \varphi(p) = p - 1

Pour une puissance d’un nombre premier

Soit \alpha \in \mathbb{N}^* . On va donc considérer n = p^{\alpha}. Pour cela, on remarque qu’un nombre est premier avec n si et seulement si il n’est pas un multiple de p. Les multiples de p sont p, 2p, \ldots, p^{\alpha} - p, p . On en a donc p^{\alpha-1} . Ainsi, en prenant le complémentaire, on obtient 

\varphi(p^{\alpha}) = p^{\alpha}-p^{\alpha-1} = p^{\alpha - 1}(p-1) 

Dans le cas général

Grâce au théorème des nombres premiers, on peut écrire n sous la forme n = \displaystyle \prod_{i=1}^r p_i^{\alpha_i}

En utilisant r-1 fois la propriété sur le produit, on obtient que \varphi(n) = \displaystyle \prod_{i=1}^r \varphi(p_i^{\alpha_i}) = \prod_{i=1}^r \left(p_i^{\alpha_i} - p_i^{\alpha_i - 1}\right)

En transformant l’expression, on obtient \varphi(n) = \displaystyle \prod_{i=1}^r p_i^{\alpha_i}\left( 1 -\dfrac{1}{p_i}\right) = \prod_{i=1}^r p_i^{\alpha_i}  \prod_{i=1}^r \left( 1 -\dfrac{1}{p_i}\right) = n  \prod_{i=1}^r \left( 1 -\dfrac{1}{p_i}\right)

C’est cette forme là qui est la plus utilisée.

Total
0
Shares

Laisser un commentaire

Articles similaires