Indicatrice d'Euler

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Les mille premières valeurs de φ(n)

En mathématiques, l'indicatrice d'Euler est une fonction arithmétique de la théorie des nombres.

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.

La fonction indicatrice est aussi appelée fonction phi d'Euler ou simplement la fonction phi, car la lettre φ est communément utilisée pour la désigner.

Elle est nommée en l'honneur du mathématicien suisse Leonhard Euler, qui fut le premier à l'étudier.

Histoire et notation[modifier | modifier le code]

Leonhard Euler a le premier étudié cette fonction dans les années 1750, mais tout d'abord sans lui donner de nom[1]. 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: "denotet character πD multitudinem istam numerorum ipso D minorum, et qui cum eo nullum habeant divisorem communem"[2]. C'est finalement en 1801 que Carl Friedrich Gauss introduit la lettre grecque ϕ, dans les Disquisitiones Arithmeticae (art. 38)[3], toujours sans user de parenthèses autour de l'argument; il écrit ainsi ϕA pour ce qui est noté maintenant ϕ(A).

Définition et calcul explicite[modifier | modifier le code]

Définition et exemple[modifier | modifier le code]

Plus formellement :

\begin{array}{ccccl}\varphi&:&\N^*&\longrightarrow&\N^*\\&&n&\longmapsto&\mathrm{card}(\{m\in\N^*~|~m\le n~\text{et}~m~\mathrm{premier~\grave a}~n\}).\end{array}

Par exemple :

  • φ(8) = 4 car parmi les nombres de 1 à 8, seuls les quatre nombres 1, 3, 5 et 7 sont premiers à 8,
  • φ(1) = 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)).
  • φ(2) = 1.

Premières propriétés[modifier | modifier le code]

Articles détaillés : Groupe cyclique et Anneau Z/nZ.

Dans ce paragraphe, n désigne un entier strictement positif.

  • La valeur φ(n) est égale à l'ordre du groupe des éléments inversibles de l'anneau Z/nZ.
    Cette propriété est démontrée dans le paragraphe Groupe des unités de l'article Anneau Z/nZ.
  • La valeur φ(n) est égale au nombre de générateurs d'un groupe cyclique d'ordre n, comme (Z/nZ, +).
    Cette propriété est déduite de la précédente dans le paragraphe Structure additive de l'article Anneau Z/nZ.
  • Si u et v sont deux entiers strictement positifs et premiers entre eux, alors φ(uv) = φ(u)φ(v).
    Une telle fonction est dite multiplicative. On peut déduire cette propriété de la précédente et du théorème des restes chinois pour les groupes, selon lequel le groupe cyclique (Z/(uv)Z, +) est isomorphe au produit (Z/uZ)×(Z/vZ). Un couple (x, y) de ce groupe produit est générateur si et seulement si x est générateur de Z/uZ et y est générateur de Z/vZ. Le nombre de générateurs du groupe produit est donc égal à φ(u)φ(v). L'isomorphisme montre que cette valeur est égale au nombre de du groupe Z/(uv)Z, ce qui démontre la formule recherchée.

Calcul[modifier | modifier le code]

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

{\rm si}\quad n=\prod_{i=1}^rp_i^{k_i}\quad{\rm alors}\quad\varphi(n)=\prod_{i=1}^r(p_i-1)p_i^{k_i-1}=n\prod_{i=1}^r{\left(1-\frac1{p_i}\right)}

où chaque pi désigne un nombre premier et ki un entier strictement positif.

En effet, calculer \quad\varphi(p_i^{k_i}) revient à compter le nombre d’entiers compris entre 1 et p_i^{k_i} (inclus) qui sont premiers avec p_i .

Comme p_i est premier, cela revient à dénombrer le nombre d’entiers qui ne sont pas divisibles par p_i , c’est-à-dire tous les entiers sauf les multiples de p_i .

Comme il y a p_i^{k_i - 1} multiples de p_i et que de façon triviale, le nombre de nombres entre 1 et p_i^{k_i} est p_i^{k_i} :

\forall i\in[1,r]\quad\varphi(p_i^{k_i})=p_i^{k_i}-p_i^{k_i - 1}=(p_i-1)p_i^{k_i-1}.

Autres propriétés[modifier | modifier le code]

Arithmétique modulaire[modifier | modifier le code]

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).
  • Un entier p > 0 est premier si et seulement si φ(p) = p – 1.
  • Si n a q diviseurs premiers impairs distincts, φ(n) est divisible par 2q.
    Ces trois propriétés peuvent se déduire du calcul explicite de φ.
  • Pour tout entier n > 2, φ(n) est pair.
    En effet, mn – 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 largement cette fonction. Le code 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, or

  • Le degré du ne polynôme cyclotomique Φn est égal à φ(n).

Une application de la formule d'inversion de Möbius est, une fois démontrée la formule

\sum_{d\mid n}\varphi(d)=n

(en partitionnant un groupe cyclique suivant les ordres de ses éléments), de la réécrire φ ✻ 1 = Id où ✻ est la convolution de Dirichlet, 1 est la fonction constante 1 et Id la fonction identité (sur les entiers strictement positifs), et d'en déduire que φ = μId c'est-à-dire

Théorie analytique des nombres[modifier | modifier le code]

Fonctions génératrices[modifier | modifier le code]

Les deux fonctions génératrices présentées ici se calculent respectivement à l'aide des deux formules φ = μId et φ ✻ 1 = Id ci-dessus.

Comme la série de Dirichlet génératrice de μ est 1/ζ(s) — où ζ est la fonction zêta de Riemann — et celle de Id est ζ(s – 1), on en déduit celle de φ (qui converge pour Re(s) > 2) :

\sum_{n=1}^{\infty}\frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.

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

\sum_{n=1}^{\infty}\frac{\varphi(n)q^n}{1-q^n}=\sum_{m=1}^{\infty}mq^m=\frac q{(1-q)^2}.

Moyenne asymptotique[modifier | modifier le code]

Arnold Walfisz (en) a établi[4]

\sum_{n\le x}\varphi(n)=\frac3{\pi^2}x^2+O\left(x(\log x)^{2/3}(\log\log x)^{4/3}\right)\ \ (x\rightarrow\infty)

(où 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 (ru). À ce jour, c'est toujours la meilleure estimation de ce type démontrée.

Croissance de la fonction[modifier | modifier le code]

La croissance de \varphi(n) comme une fonction de n est une question intéressante. Asymptotiquement, nous avons

n^{1 - \epsilon} < \varphi(n) \le n-1\

pour n'importe quel \epsilon > 0\, et n > N(\epsilon)\, . L'égalité à la borne supérieure est satisfaite chaque fois que n est un nombre premier. Et si nous considérons la relation

\frac {\varphi(n)}{n}=\prod_{p|n}(1 - p^{-1})\,

nous pouvons constater que les valeurs de n correspondant aux valeurs particulièrement petites de la fonction d'Euler sont les n 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

 \frac{{\rm e}^{-\gamma}n}{\ln\ln n}(1+o(1)) < \varphi(n) \le n-1\

(où o est le petit o de Landau), et que la minoration est optimale.

Les 99 premières valeurs de la fonction φ[modifier | modifier le code]

Les 100 premières valeurs de la fonction φ
\varphi(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+   1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88
90+ 24 72 44 60 46 72 32 96 42 60

Autres formules impliquant la fonction φ d'Euler[modifier | modifier le code]

Inégalités[modifier | modifier le code]

Certaines inégalités impliquant la fonction φ sont :


\varphi(n) > \frac n{{\rm e}^\gamma\; \log \log n + \frac3{\log \log n}}
pour n > 2[12],[13],

\varphi(n) \ge \sqrt{\frac n2}
pour n > 0

et


\varphi(n) \ge \sqrt n
pour n > 6.

On a déjà remarqué que pour n premier, φ(n) = n – 1. Pour un nombre composé n, nous avons 
\varphi(n)\le n-\sqrt n.

Par conséquent, pour tout n > 1 : 0<\frac{\varphi(n)}n<1.

Pour un grand n 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 φ(n)/n.

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


\frac{6n^2}{\pi^2}<\varphi(n)\sigma(n)<n^2
\mbox{ pour }n>1.

Conjectures[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. L. Euler, Theoremata arithmetica nova methodo demonstrata, Novi Commentarii academiae scientiarum Petropolitanae, vol. 8, (1763), pp. 74-104, ou Opera Omnia, Series 1, Volume 2, pp. 531-555. Le traité a été présenté devant l'académie de St-Petersbourg le 15 octobre 1759. Un traité du même nom a été lu à l'académie de Berlin le 8 juin 1758.
  2. L. Euler, Speculationes circa quasdam insignes proprietates numerorum, Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), pp. 18-30, ou Opera Omnia, Series 1, Volume 4, pp. 105-115. Le traité a été présenté devant l'Académie de St-Pétersbourg le 9 octobre 1775.
  3. [1]
  4. a et b (de) A. Walfisz, Weylsche Exponentialsummen in der neueren Zahlentheorie, Berlin, VEB deutscher Verlag der Wissenschaften,‎ 1963.
  5. (en) László Tóth, Menon's Identity and arithmetical sums representing functions of several variables, arXiv:1103.5861v2, eq. 1.
  6. Tóth, eq. 5.
  7. Tóth, eq. 3.
  8. Tóth, eq. 35.
  9. Tóth, eq. 2.
  10. Tóth écrit que Menon l'a prouvé en 1965 pour f multiplicative, et V. Sita Ramaiah pour f quelconque.
  11. a et b (en) R. Sitaramachandrarao, « On an error term of Landau II », Rocky Mountain J. Math., vol. 15,‎ 1985, p. 579-588.
  12. (en) Eric Bach (en) et Jeffrey Shallit, Algorithmic Number Theory (Vol I: Efficient Algorithms), MIT Press,‎ 1996 (ISBN 978-0-262-02405-1, lire en ligne), p. 234.
  13. (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer,‎ 1996, 3e éd. (ISBN 978-0-387-94457-9), p. 320.

(en)/(en) Cet article est partiellement ou en totalité issu des articles intitulés en anglais « Euler's totient function » (voir la liste des auteurs) et en anglais « Arithmetic function » (voir la liste des auteurs).