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 Modèle:Mvar non nul associe le nombre d'entiers compris entre 1 et Modèle:Mvar (inclus) et premiers avec Modèle:Mvar.
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 <math>\varphi</math> (ou <math>\phi</math>) 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<ref>Modèle:Article, ou Opera Omnia, Series 1, vol. 2, Modèle:P.. Le traité a été présenté devant l'Académie de Saint-Pétersbourg le 15 octobre 1759. Un traité du même nom a été lu à l'académie de Berlin le 8 juin 1758.</ref>. 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 Modèle:MathPi, sans parenthèses autour de l'argument : Modèle:Latin<ref>Modèle:Article, ou Opera Omnia, Series 1, vol. 4, Modèle:P.. Le traité a été présenté devant l'Académie de Saint-Pétersbourg le 9 octobre 1775.</ref>. C'est finalement en 1801 que Carl Friedrich Gauss introduit la lettre grecque Modèle:Mvar, dans les Disquisitiones Arithmeticae (art. 38)<ref>Modèle:Ouvrage.</ref>, toujours sans user de parenthèses autour de l'argument ; il écrit ainsi Modèle:Mvar pour ce qui est noté maintenant Modèle:Math. De nos jours, on emploie la lettre grecque phi minuscule en italique Modèle:Mvar ou Modèle:Mvar.
En 1879, J. J. Sylvester invente le terme de totient pour désigner cette fonction<ref>Modèle:Ouvrage</ref>, de sorte qu'elle est généralement désignée sous le terme de Modèle:Citation étrangère dans les écrits anglophones. Le terme totient est employé pour la fonction totient de Jordan, qui est une généralisation de l'indicatrice d'Euler.
Définition et exemples
L'indicatrice d'Euler est la fonction Modèle:Mvar, de l'ensemble ℕ* des entiers strictement positifs dans lui-même, définie par :
Par exemple :
- Modèle:Math car parmi les nombres de 1 à 8, seuls les quatre nombres 1, 3, 5 et 7 sont premiers avec 8 ;
- Modèle:Math car parmi les nombres de 1 à 12, seuls les quatre nombres 1, 5, 7 et 11 sont premiers avec 12 ;
- un entier Modèle:Mvar > 1 est premier si et seulement si tous les nombres de 1 à Modèle:Mvar – 1 sont premiers avec Modèle:Mvar, Modèle:C.-à-d. si et seulement si Modèle:Math(Modèle:Mvar) = Modèle:Mvar – 1 ;
- Modèle:Math 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 Modèle:Mvar > 1, on peut remplacer non seulement Modèle:Mvar ∈ ℕ* par Modèle:Mvar ∈ ℕ mais Modèle:Mvar ≤ Modèle:Mvar par m < Modèle:Mvar, dans la définition ci-dessus de Modèle:Math(Modèle:Mvar)).
On trouvera ci-dessous les 99 premières valeurs de la fonction Modèle:Mvar (suite Modèle:OEIS2C de l'OEIS).
| <math>\varphi(n)</math> | +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 |
Premières propriétés
Calcul
La valeur de l'indicatrice d'Euler s'obtient à partir de la décomposition en facteurs premiers de Modèle:Mvar :
où chaque Modèle:Mvari désigne un nombre premier et Modèle:Mvari un entier strictement positif : on peut le déduire du théorème précédent<ref name=Wikiversité/> ou, plus élémentairement, du principe d'inclusion-exclusion.
Par exemple, pour les nombres sans facteurs carré <math>n=\prod_{i=1}^rp_i</math>, comme par exemple les primorielles, on obtient <math>\quad\varphi(n)=\prod_{i=1}^r(p_i-1)</math>.
Algorithme de calcul
À ce jour, on ne connaît pas d’algorithme efficace pour calculer l’indicatrice d’Euler d’un entier Modèle:Mvar donné. L’expression ci‐dessus requiert de calculer les facteurs premiers de Modèle:Mvar, 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.
Transformée de Fourier
L'indicatrice d'Euler est la transformée de Fourier discrète du PGCD, évaluée en 1<ref>Modèle:Article</ref>.
Soit
- <math> \mathcal{F} \{ \mathbf{x} \}[m] = \sum\limits_{k=1}^n x_k \cdot \mathrm{e}^{-2\mathrm{i}\pi\frac{mk}{n}}</math>
où Modèle:Math pour Modèle:Math. Alors
- <math>\varphi (n) = \mathcal{F} \{ \mathbf{x} \}[1] = \sum\limits_{k=1}^n \mathrm{PGCD}(k,n) \mathrm{e}^{-2\mathrm{i}\pi\frac{k}{n}}.</math>
La partie réelle de la formule est
- <math>\varphi (n)=\sum\limits_{k=1}^n \mathrm{PGCD}(k,n) \cos \left(\frac{2\pi k}{n}\right).</math>
Par exemple, en utilisant <math>\cos\tfrac{\pi}5 = \tfrac{\sqrt 5+1}4 </math> et <math>\cos\tfrac{2\pi}5 = \tfrac{\sqrt 5-1}4 </math>: <math display="block">\begin{array}{rcl} \varphi(10) &=& \mathrm{PGCD}(1,10)\cos\tfrac{2\pi}{10} + \mathrm{PGCD}(2,10)\cos\tfrac{4\pi}{10} + \mathrm{PGCD}(3,10)\cos\tfrac{6\pi}{10}+\cdots+\mathrm{PGCD}(10,10)\cos\tfrac{20\pi}{10}\\ &=& 1\cdot(\tfrac{\sqrt5+1}4) + 2\cdot(\tfrac{\sqrt5-1}4) + 1\cdot(-\tfrac{\sqrt5-1}4) + 2\cdot(-\tfrac{\sqrt5+1}4) + 5\cdot (-1) \\ && +\ 2\cdot(-\tfrac{\sqrt5+1}4) + 1\cdot(-\tfrac{\sqrt5-1}4) + 2\cdot(\tfrac{\sqrt5-1}4) + 1\cdot(\tfrac{\sqrt5+1}4) + 10 \cdot (1) \\ &=& 4 . \end{array} </math>
Contrairement au produit d'Euler et la formule de la somme des diviseurs, Celle-ci ne requiert pas de connaître les facteurs de Modèle:Mvar. Cependant, elle implique le calcul du PGCD de Modèle:Mvar et de tous les entiers positifs inférieurs à Modèle:Mvar, ce qui suffit par ailleurs à donner la factorisation.
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. Modèle:Énoncé Modèle:Énoncé Ces deux propriétés peuvent se déduire du [[#Calcul|calcul explicite de Modèle:Mvar]]. Modèle:Énoncé En effet, Modèle:Math est une bijection entre les entiers premiers à Modèle:Mvar compris entre 0 (ou 1) et Modèle:Math et ceux compris entre Modèle:Math et Modèle:Mvar, et Modèle:Math peut être entier mais pas premier à Modèle:Mvar. Modèle:Énoncé
La formule d'inversion de Möbius donne alors :
où Modèle:Mvar désigne la fonction de Möbius.
Applications
- La cryptologie utilise cette fonction. Le chiffrement RSA se fonde sur la propriété suivante (théorème d'Euler) :
- 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 Modèle:Mvar-ième polynôme cyclotomique Modèle:Math est égal à Modèle:Math.
Théorie analytique des nombres
Fonctions génératrices
Les deux formules Modèle:Math et Modèle:Math, présentées ci-dessus, où ✻ désigne la convolution de Dirichlet, permettent de calculer respectivement les fonctions génératrices de Dirichlet et de Lambert.
Comme la série de Dirichlet génératrice de Modèle:Math est Modèle:Math — où Modèle:Math est la fonction zêta de Riemann — et celle de Modèle:Math est Modèle:Math, on en déduit celle de Modèle:Math (qui converge pour Modèle:Math) :
La série de Lambert associée à Modèle:Math (qui converge pour |q| < 1) est
Moyenne asymptotique
Arnold Walfisz a établi<ref name=Walfisz>Modèle:Ouvrage.</ref>
(où Modèle:Math 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, on a
- <math>n^{1 - \varepsilon} < \varphi(n) \leqslant n-1\ </math>
pour n'importe quel <math>\varepsilon > 0\,</math> et <math>n > N(\varepsilon)\,</math> . L'égalité à la borne supérieure est satisfaite chaque fois que n est un nombre premier. Et si on considère la relation
- <math>\frac {\varphi(n)}{n}=\prod_{p|n,\ p\text{ premier}}(1 - p^{-1})\,</math>
on peut constater que les valeurs de Modèle:Mvar correspondant aux Modèle:Pas clair de <math>\frac{\varphi(n)}n</math> sont les Modèle:Mvar 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
- <math> \frac{{\rm e}^{-\gamma}n}{\ln\ln n}(1+o(1)) < \varphi(n) \leqslant n-1\ </math>
(où Modèle:Math est le petit o de Landau et <math>\gamma</math> est la constante d'Euler-Mascheroni), et que la minoration est optimale.
Autres formules impliquant la fonction φ d'Euler
- <math>\forall n>0, \ \forall a>1 \quad n|\varphi(a^n-1)</math>
car l'ordre multiplicatif de Modèle:Math modulo Modèle:Math vaut Modèle:Math. - <math>\varphi(mn)=\varphi(m)\varphi(n)\frac d{\varphi(d)}\text{ pour }d={\rm pgcd}(m,n),</math>
en particulier :- <math>\varphi(2m)=\begin{cases}2\varphi(m)&\text{ si }m\text{ est pair}\\\varphi(m)&\text{ si }m\text{ est impair}\end{cases}</math>
- <math>\forall k\ge1\quad\varphi(n^k)=n^{k-1}\varphi(n).</math>
- <math>\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}.</math>
- <math>\forall n>1\quad\sum_{1\le k\le n\atop{\rm pgcd}(k,n)=1}k=\frac12n\varphi(n).</math>
- <math>\sum_{k=1}^n\varphi(k)=\frac12\left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac nk\right\rfloor^2\right).</math>
- En 1965, P. Kesava Menon a démontré<ref>{{#invoke:Langue|indicationDeLangue}} László Tóth, Menon's Identity and arithmetical sums representing functions of several variables, Modèle:Arxiv2, eq. 1.</ref>Modèle:Retraitoù Modèle:Math est la fonction nombre de diviseurs
Modèle:Démonstration/début B. Sury<ref>Tóth, eq. 5.</ref> Modèle:Retrait où σa est la fonction somme des puissances a-ièmes des diviseurs.
N. Rao<ref>Tóth, eq. 3.</ref> Modèle:Retrait où Modèle:Math sont des entiers tels que Modèle:Math et Modèle:Math est la fonction totient de Jordan.
L. Tóth<ref>Tóth, eq. 35.</ref> Modèle:Retrait \varphi({\rm pgcd}(d_1, d_2))2^{\omega({\rm ppcm}(d_1, d_2))}</math>}} où Modèle:Math et Modèle:Math sont impairs, Modèle:Math et ω est la fonction nombre de diviseurs premiers distincts.
En fait, pour toute fonction arithmétique Modèle:Math<ref>Tóth, eq. 2.</ref>,<ref>Tóth écrit que Menon l'a prouvé en 1965 pour Modèle:Math multiplicative, et V. Sita Ramaiah pour Modèle:Math quelconque.</ref>, Modèle:Retrait Modèle:Démonstration/fin
- <math>\sum_{k=1}^n\frac{\varphi(k)}k=\sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor=\frac6{\pi^2}n+O\left((\log n)^{2/3}(\log\log n)^{4/3}\right)</math> <ref name=Walfisz/>.
- <math>\sum_{k=1}^n\frac k{\varphi(k)}=\frac{315~\zeta(3)}{2\pi^4}n-\frac{\log n}2+O\left((\log n)^{2/3}\right)</math> <ref name=Sitaramachandrarao>Modèle:Article.</ref>.
- <math>\sum_{k=1}^n\frac1{\varphi(k)} = \frac{315~\zeta(3)}{2\pi^4}\left(\log n+\gamma-\sum_{p\text{ premier}}\frac{\log p}{p^2-p+1}\right)+O\left(\frac{(\log n)^{2/3}}n\right)</math> <ref name=Sitaramachandrarao/>
(Modèle:Math est la constante d'Euler). - <math>\forall m>1\quad\sum_{1\le k\le n\atop{\rm pgcd}(k,m)=1}1=n\frac{\varphi(m)}m+O\left(2^{\omega(m)}\right)</math>
où [[Fonction additive (arithmétique)#Exemples de fonctions qui sont seulement additives|ω(Modèle:Mvar)]] est le nombre de diviseurs premiers de Modèle:Mvar distincts.
Inégalités
Voici quelques inégalités impliquant la fonction Modèle:Math :
- <math>
\varphi(n) > \frac n{{\rm e}^\gamma\; \log \log n + \frac3{\log \log n}} </math> pour Modèle:Math<ref>Modèle:Ouvrage.</ref>,<ref>Modèle:Ouvrage.</ref>,
- <math>
\varphi(n) \geqslant \sqrt{\frac n2} </math> pour Modèle:Math
et
- <math>
\varphi(n) \geqslant \sqrt n </math> pour Modèle:Math.
On a déjà remarqué que pour Modèle:Math premier, Modèle:Math. Pour un nombre composé Modèle:Math, nous avons Modèle:Retrait
Par conséquent, pour tout Modèle:Math : Modèle:Retrait
Pour un grand Modèle:Mathalé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 Modèle:Math.
Deux inégalités combinant la fonction Modèle:Math et la fonction somme des diviseurs Modèle:Math sont :
Conjectures
Les résultats ci-dessous ne sont encore que des conjectures à l'heure actuelle :
- <math>n</math> est premier si (et seulement si) <math>n \equiv 1\bmod \varphi(n)</math> (c'est le problème de Lehmer, énoncé par Derrick Lehmer)
- <math>\forall{n > 0}\quad\exists{m \neq n}\quad\varphi(n)=\varphi(m)</math> (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).
Nombres remarquables
À partir de la fonction indicatrice d'Euler et de fonctions proches, diverses familles de nombres remarquables peuvent être définies.
Fonction indicatrice
Modèle:Article détaillé Un nombre totient est un nombre entier appartenant à l'image de la fonction indicatrice d'Euler : c'est-à-dire un entier m pour lequel il existe au moins un n pour lequel φ(n) = m. La valence ou multiplicité d'un nombre totient m est le nombre de solutions à cette équation<ref>Modèle:Ouvrage</ref>.
Un nombre nontotient est un entier naturel qui n'est pas un nombre totient. Tout nombre entier impair supérieur à 1 est trivialement un nontotient. Il existe également une infinité de nontotients pairs<ref>Modèle:Ouvrage</ref>, et chaque entier positif a un multiple qui est un nontotient pair<ref>Modèle:Article</ref>.
Un nombre hautement totient est un entier totient dont la multiplicité est supérieure à celle de n'importe quel entier positif inférieur à lui.
Fonction cototient
Modèle:Article détaillé La fonction cototient est définie à partir de l'indicatrice d'Euler, comme Modèle:Math : elle associe à tout entier naturel Modèle:Mvar non nul le nombre Modèle:Math. Ce nombre représente le nombre d'entiers compris entre 1 et Modèle:Mvar (inclus) et qui ne sont pas premiers avec Modèle:Mvar (de manière équivalente, qui ont avec Modèle:Mvar au moins un facteur premier commun). À partir de la fonction cototient, sont définies de manière équivalente les nombres cototients, noncototients et hautement cototients.
Un nombre cototient est un nombre entier appartenant à l'image de la fonction cototient : c'est-à-dire un entier Modèle:Mvar pour lequel il existe au moins un Modèle:Mvar pour lequel Modèle:Math. La valence ou multiplicité d'un nombre cototient Modèle:Mvar est le nombre de solutions à cette équation.
Un nombre noncototient est un entier naturel qui n'est pas un nombre cototient, c'est-à-dire un entier Modèle:Mvar n'admettant pas d'antécédent par la fonction cototient. De manière équivalente, exprimé algébriquement, ce sont les entiers Modèle:Mvar tels que l'équation Modèle:Math ne possède pas de solution.
Un nombre hautement cototient est un entier cototient dont la multiplicité est supérieure à celle de n'importe quel entier positif inférieur à lui. De manière équivalente, exprimé algébriquement, ce sont les entiers Modèle:Mvar tels que l'équation Modèle:Math possède plus de solution que chacune des équations Modèle:Math pour tout Modèle:Math.
Notes et références
Modèle:Traduction/Référence Modèle:Références
