Indicatrice d'Euler
En mathématiques, l'indicatrice d'Euler est une fonction arithmétique de la théorie des nombres, qui à tout entier naturel n non nul associe le nombre d'entiers compris entre 1 et n (inclus) et premiers avec n.

Elle intervient en mathématiques pures, à la fois en théorie des groupes, en théorie algébrique des nombres et en théorie analytique des nombres.

En mathématiques appliquées, à travers l'arithmétique modulaire, elle joue un rôle important en théorie de l'information et plus particulièrement en cryptologie.

L'indicatrice d'Euler est aussi appelée indicateur d'Euler, fonction phi d'Euler ou simplement fonction phi, car la lettre  (ou ) est communément utilisée pour la désigner.

Elle porte le nom du mathématicien suisse Leonhard Euler, qui fut le premier à l'étudier.

Histoire et notation 

Leonhard Euler a le premier étudié cette fonction dans les années 1750, mais tout d'abord sans lui donner de nom. Ce n'est qu'en 1784, dans un article où il reprend l'étude de cette fonction, qu'il utilise pour la dénoter la lettre grecque π, sans parenthèses autour de l'argument : . C'est finalement en 1801 que Carl Friedrich Gauss introduit la lettre grecque ϕ, dans les Disquisitiones Arithmeticae (art. 38), toujours sans user de parenthèses autour de l'argument ; il écrit ainsi ϕA pour ce qui est noté maintenant ϕ(A). De nos jours, on emploie la lettre grecque phi minuscule en italique  ou .

Définition et exemples 

L'indicatrice d'Euler est la fonction , de l'ensemble ℕ des entiers strictement positifs dans lui-même, définie par :

Par exemple :
  car parmi les nombres de 1 à 8, seuls les quatre nombres 1, 3, 5 et 7 sont premiers avec 8 ;
  car parmi les nombres de 1 à 12, seuls les quatre nombres 1, 5, 7 et 11 sont premiers avec 12 ;
un entier p > 1 est premier si et seulement si tous les nombres de 1 à p – 1 sont premiers avec p,  si et seulement si (p) = p – 1 ;
  car 1 est premier avec lui-même (c'est le seul entier naturel qui vérifie cette propriété, si bien que pour tout entier n > 1, on peut remplacer non seulement m ∈ ℕ* par m ∈ ℕ mais m ≤ n par m < n, dans la définition ci-dessus de (n)).
On trouvera ci-dessous les 99 premières valeurs de la fonction φ (suite  de l'OEIS).

Premières propriétés

Calcul 
La valeur de l'indicatrice d'Euler s'obtient à partir de la décomposition en facteurs premiers de n :

où chaque pi désigne un nombre premier et ki un entier strictement positif : on peut le déduire du théorème précédent ou, plus élémentairement, du principe d'inclusion-exclusion.

Par exemple, pour les nombres sans facteurs carré , comme par exemple les primorielles, on obtient .

Algorithme de calcul 

À ce jour, on ne connait pas d’algorithme efficace pour calculer l’indicatrice d’Euler d’un entier n donné. L’expression ci‐dessus requiert de calculer les facteurs premiers de n, ce qui est réputé difficile : les meilleurs algorithmes de factorisation connus ont une complexité sous‐exponentielle.

Le problème du calcul de l’indicatrice d’Euler est plus général que le problème RSA car il permet de résoudre facilement ce dernier. Par conséquent, la connaissance d’un algorithme de calcul efficace casserait la sécurité du système cryptographique RSA.

Autres propriétés

Arithmétique modulaire 
L'indicatrice d'Euler est une fonction essentielle de l'arithmétique modulaire ; elle est à la base de résultats fondamentaux, à la fois en mathématiques pures et appliquées.
 Si a divise b alors (a) divise (b).
 Si n a q diviseurs premiers impairs distincts, (n) est divisible par 2.Ces trois propriétés peuvent se déduire du calcul explicite de .
 Pour tout entier n > 2, (n) est pair et la somme de tous les entiers positifs inférieurs et premiers à n est égale à n.En effet, m ↦ n – m est une bijection entre les entiers premiers à n compris entre 0 (ou 1) et n/2 et ceux compris entre n/2 et n, et n/2 peut être entier mais pas premier à n.
 La cryptologie utilise cette fonction. Le chiffrement RSA se fonde sur la propriété suivante :(Théorème d'Euler). Si n est un entier strictement positif et a un entier premier à n, alors a(n) ≡ 1 (modulo n).
 Une autre branche de la théorie de l'information utilise l'indicatrice : la théorie des codes. C'est les cas des codes correcteurs, et particulièrement des codes cycliques. Ce type de code se construit à l'aide d'un polynôme cyclotomique, orLe degré du n-ième polynôme cyclotomique Φn est égal à (n).
 Dans le groupe (ℤ/nℤ, +), les éléments d'ordre d (un diviseur de n) sont les générateurs du sous-groupe engendré par . Si les éléments de ℤ/nℤ sont partitionnés selon leurs ordres, on obtient donc :.
 La formule d'inversion de Möbius donne alors :,où  désigne la fonction de Möbius.
 (n) est égal à la valeur en 1 de la transformée de Fourier discrète de pgcd(n, –), donc aussi à sa partie réelle :

 Théorie analytique des nombres 
 Fonctions génératrices 
Les deux fonctions génératrices présentées ici se calculent respectivement à l'aide des deux formules  =  ✻  et  ✻  ci-dessus.

Comme la série de Dirichlet génératrice de  est  — où  est la fonction zêta de Riemann — et celle de  est , on en déduit celle de  (qui converge pour ) :

La série de Lambert associée à  (qui converge pour |q| < 1) est

 Moyenne asymptotique 
Arnold Walfisz a établi

(où  est le grand O de Landau), en exploitant entre autres des estimations de sommes d'exponentielles dues à I. M. Vinogradov et à N. M. Korobov. À ce jour, c'est toujours la meilleure estimation de ce type démontrée.

 Croissance de la fonction 
Asymptotiquement, nous avons

 

pour n'importe quel  et  .
L'égalité à la borne supérieure est satisfaite chaque fois que n est un nombre premier. Et si nous considérons la relation

 

nous pouvons constater que les valeurs de n correspondant aux  de  sont les n primoriels, c’est-à-dire ceux qui sont le produit d'un segment initial de la suite de tous les nombres premiers. À partir du troisième théorème de Mertens et des inégalités de Tchebychev on peut montrer que l'estimation ci-dessus peut être remplacée par

 

(où  est le petit o de Landau et  est la constante d'Euler-Mascheroni), et que la minoration est optimale.

 Autres formules impliquant la fonction φ d'Euler 
 car l'ordre multiplicatif de  modulo  vaut .
 en particulier :
 
 
 
 
 
 En 1965, P. Kesava Menon a démontréoù  est la fonction nombre de diviseurs

B. Sury

où σ est la fonction somme des puissances a-ièmes des diviseurs.

N. Rao

où  sont des entiers tels que  et  est la fonction totient de Jordan.

L. Tóth

où  et  sont impairs,  et ω est la fonction nombre de diviseurs premiers distincts.

En fait, pour toute fonction arithmétique ,

  .
  .
  ( est la constante d'Euler).
 où ω(m) est le nombre de diviseurs premiers de m distincts.

 Inégalités 
Certaines inégalités impliquant la fonction  sont :
 pour ,

 pour 

et
 pour .

On a déjà remarqué que pour  premier, . Pour un nombre composé , nous avons

Par conséquent, pour tout  :

Pour un grand aléatoire, ces bornes 0 et 1 ne peuvent pas être améliorées. En effet, ce sont les limites inférieure et supérieure de .

Deux inégalités combinant la fonction '' et la fonction somme des diviseurs  sont :

Conjectures 

  est premier si (et seulement si)  (c'est le problème de Lehmer, énoncé par Derrick Lehmer)
  (c'est la « conjecture de Carmichael » que Robert Daniel Carmichael, en 1907, a énoncée et cru démontrer, mais qui reste toujours un problème ouvert).

Notes et références

Articles connexes 

Arithmétique modulaire
Leonhard Euler
Théorie analytique des nombres