Voir la source de Indicatrice d'Euler

{{redirect confusion|Fonction phi d'Euler|Fonction d'Euler}}
[[Fichier:EulerPhi.svg|vignette|upright=1.5|Les mille premières valeurs de {{math|''φ''(''n'')}}.]]
En [[mathématiques]], l''''indicatrice d'Euler''' est une [[fonction arithmétique]] de la [[théorie des nombres]], qui à tout [[entier naturel]] {{Mvar|n}} non nul associe le nombre d'entiers compris entre 1 et {{Mvar|n}} (inclus) et [[Nombres premiers entre eux|premiers avec]] {{Mvar|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 [[Phi|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>{{article|lang=la|auteur=L. Euler |lire en ligne=http://math.dartmouth.edu/~euler/docs/originals/E271.pdf |titre=Theoremata arithmetica nova methodo demonstrata |périodique=Novi Commentarii academiae scientiarum Petropolitanae |volume=8 |année=1763 |pages={{p.|74-104}}}}, ou ''Opera Omnia'', Series 1, vol. 2, {{p.|531-555}}. Le traité a été présenté devant l'[[Académie des sciences de Saint-Pétersbourg|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 {{mathPi}}, sans parenthèses autour de l'argument : {{latin|denotet character πD multitudinem istam numerorum ipso D minorum, et qui cum eo nullum habeant divisorem communem}}<ref>{{article|lang=la|auteur=L. Euler |lire en ligne=http://math.dartmouth.edu/~euler/docs/originals/E564.pdf |titre=Speculationes circa quasdam insignes proprietates numerorum |périodique=Acta Academiae Scientarum Imperialis Petropolitinae |volume=4 |année=1784 |pages={{p.|18-30}}}}, ou ''Opera Omnia'', Series 1, vol. 4, {{p.|105-115}}. 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 {{mvar|ϕ}}, dans les ''[[Disquisitiones Arithmeticae]]'' (art. 38)<ref>{{ouvrage|lang=la |auteur=Carl Friedrich Gauss |titre=Disquisitiones arithmeticae |lire en ligne=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN235993352&DMDID=DMDLOG_0007&LOGID=LOG_0007&PHYSID=PHYS_0036}}.</ref>, toujours sans user de parenthèses autour de l'argument ; il écrit ainsi {{mvar|ϕA}} pour ce qui est noté maintenant {{math|''ϕ''(''A'')}}. De nos jours, on emploie la lettre grecque phi minuscule en [[Italique (typographie)#Usages|italique]] {{mvar|ϕ}} ou {{mvar|φ}}.

En 1879, [[James Joseph Sylvester|J. J. Sylvester]] invente le terme de ''totient'' pour désigner cette fonction<ref>{{Ouvrage|langue=en|auteur1=[[James Joseph Sylvester]]|titre=American Journal of Mathematics|passage=361|éditeur=Johns Hopkins University Press|date=1879|lire en ligne=https://books.google.fr/books?id=-AcPAAAAIAAJ&pg=PA361&redir_esc=y#v=onepage&q&f=false|consulté le=2022-04-18|titre chapitre=On certain ternary cubic-form equations}}</ref>, de sorte qu'elle est généralement désignée sous le terme de {{citation étrangère|lang=en|Euler's totient function}} 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 {{mvar|φ}}, de [[Entier naturel#Notations|l'ensemble ℕ{{exp|*}} des entiers strictement positifs]] dans lui-même, définie par :<center><math>\begin{array}{ccccl}\varphi&:&\N^*&\longrightarrow&\N^*\\&&n&\longmapsto&\mathrm{card}
(\{m\in\N^*~|~m\leqslant n~\text{et}~m~\mathrm{premier~avec}~n\}).\end{array}</math></center>

Par exemple :
* {{math|1=''φ''(8) = 4}} car parmi les nombres de 1 à 8, seuls les quatre nombres [[1 (nombre)|1]], [[3 (nombre)|3]], [[5 (nombre)|5]] et [[7 (nombre)|7]] sont premiers avec [[8 (nombre)|8]] ;
* {{math|1=''φ''(12) = 4}} car parmi les nombres de 1 à 12, seuls les quatre nombres [[1 (nombre)|1]], [[5 (nombre)|5]], [[7 (nombre)|7]] et [[11 (nombre)|11]] sont premiers avec [[12 (nombre)|12]] ;
*un entier {{math|''p'' > 1}} est [[nombre premier|premier]] [[Équivalence logique|si et seulement si]] ''tous'' les nombres de 1 à {{math|''p'' – 1}} sont premiers avec {{Mvar|p}}, {{c.-à-d.}} si et seulement si {{math|''φ''(''p'') {{=}} ''p'' – 1}} ;
* {{math|1=''φ''(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 {{Mvar|n}} > 1, on peut remplacer non seulement {{Mvar|m}} ∈ ℕ* par {{Mvar|m}} ∈ ℕ mais {{Math|''m'' ≤ ''n''}} par {{math|''m'' < ''n''}}, dans la définition ci-dessus de {{math|''φ''(''n'')}}).
On trouvera ci-dessous les 99 premières valeurs de la fonction {{mvar|φ}} (suite {{OEIS2C|A000010}} de l'[[OEIS]]). [[Fichier:EulerPhi100.svg|vignette|upright=2|droite|Les 100 premières valeurs de la fonction {{math|φ}}.]]
{| class="wikitable"
! <math>\varphi(n)</math>
! +0 || +1 || +2 || +3 || +4 || +5 || +6 || +7 || +8 || +9
|- 
! 0+ 
| &nbsp; || 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 ==
[[Fichier:Hendecagones.gif|vignette|506x506px|Les <math>\varphi(11)/2=5</math> [[Hendécagone|hendécagones]] réguliers (à 11 sommets)]]{{Théorème|nom=Théorème<ref name=Wikiversité>{{Note autre projet|Wikiversité|Introduction à la théorie des nombres/Nombres premiers et fonctions arithmétiques#Fonctions arithmétiques|« Fonctions arithmétiques », dans la leçon « Introduction à la théorie des nombres »|début=Pour une démonstration, voir par exemple}}</ref>|1=
|style=display:table|énoncé=<br>
*Pour tout entier {{math|''n''}} strictement positif, {{math|''φ''(''n'')}} est égal :
**au nombre d'[[Anneau ℤ/nℤ#Groupe des unités|éléments inversibles de l'anneau ℤ/''n''ℤ]] ;
**au nombre de [[Partie génératrice d'un groupe|générateurs]] d'un [[Groupe (mathématiques)|groupe]] [[Groupe cyclique|cyclique]] d'[[Ordre (théorie des groupes)|ordre]] ''n''.
**au nombre de [[racine de l'unité|racines n-ièmes de l'unité]] qui sont primitives.
** pour ''n'' supérieur ou égal à trois, au double du nombre de [[polygone régulier|polygones réguliers]] croisés ou non à ''n'' sommets (ou côtés).
*La fonction {{math|''φ''}} est [[Fonction multiplicative|multiplicative]], c'est-à-dire que si ''u'' et ''v'' sont deux entiers strictement positifs [[Nombres premiers entre eux|premiers entre eux]], alors {{math|''φ''}}(''uv'') = {{math|''φ''}}(''u''){{math|''φ''}}(''v'').}}

== Calcul ==
La valeur de l'indicatrice d'Euler s'obtient à partir de la [[décomposition en facteurs premiers]] de ''{{Mvar|n}}'' :
<center><math>{\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)}</math></center>

où chaque ''{{Mvar|p}}<sub>i</sub>'' désigne un nombre premier et ''{{Mvar|k}}<sub>i</sub>'' 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 [[Entier sans facteur carré|nombres sans facteurs carré]] <math>n=\prod_{i=1}^rp_i</math>, comme par exemple les [[Primorielle|primorielles]], on obtient <math>\quad\varphi(n)=\prod_{i=1}^r(p_i-1)</math>.

=== Algorithme de calcul ===

En 2025, on ne connaît pas d’[[algorithme]] [[Complexité des algorithmes|efficace]] pour calculer l’indicatrice d’Euler d’un entier ''{{Mvar|n}}'' donné. L’expression ci‐dessus requiert de calculer les facteurs premiers de ''{{Mvar|n}}'', ce qui est réputé difficile : les meilleurs [[Décomposition en produit de facteurs premiers#Algorithmes de factorisation|algorithmes de factorisation]] connus ont une complexité sous‐exponentielle.

Le [[Problème algorithmique|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 [[Chiffrement RSA|système cryptographique RSA]].

=== Transformée de Fourier ===
L'indicatrice d'Euler est la [[transformée de Fourier discrète]] du [[Plus grand commun diviseur|PGCD]], évaluée en 1<ref>{{article|lang=en |auteur1= Wolfgang Schramm | numéro = 8(1) 
 | périodique = Electronic Journal of Combinatorial Number Theory
 | titre = The Fourier transform of functions of the greatest common divisor
 | volume = A50
 | année = 2008
 |url=http://www.integers-ejcnt.org/vol8.html }}</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ù {{math|''x<sub>k</sub>'' {{=}} PGCD(''k'',''n'')}} pour {{math|''k'' ∈ {1, ..., ''n''}<nowiki/>}}. 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 {{mvar|n}}. Cependant, elle implique le calcul du PGCD de {{mvar|n}} et de tous les entiers positifs inférieurs à {{mvar|n}}, 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.
{{énoncé|Si {{mvar|a}} [[divise]] {{mvar|b}} alors {{math|''φ''(''a'')}} divise {{math|''φ''(''b'')}}.}}
{{énoncé|Si {{mvar|n}} a {{mvar|q}} [[diviseur]]s premiers [[Parité (arithmétique)|impairs]] distincts, {{math|''φ''(''n'')}} est divisible par {{math|2{{exp|''q''}}}}.}}
Ces deux propriétés peuvent se déduire du [[#Calcul|calcul explicite de {{mvar|φ}}]].
{{énoncé|Pour tout entier {{math|''n'' > 2}}, {{math|''φ''(''n'')}} est pair et la somme de tous les entiers positifs inférieurs et premiers à {{mvar|n}} est égale à {{sfrac|''n φ''(''n'')|2}}.}}
En effet, {{math|''m ''↦ ''n – m''}} est une [[bijection]] entre les entiers premiers à {{mvar|n}} compris entre 0 (ou 1) et {{math|''n''/2}} et ceux compris entre {{math|''n''/2}} et {{mvar|n}}, et {{math|''n''/2}} peut être entier mais pas premier à {{mvar|n}}.
{{énoncé|Dans le groupe {{math|(ℤ/''n''ℤ, +)}}, les éléments d'ordre {{mvar|d}} (un diviseur de {{mvar|n}}) sont les générateurs du sous-groupe engendré par {{mvar|{{surligner|''n''/''d''}}}}. Si les éléments de {{mvar|ℤ/''n''ℤ}} sont [[partition (mathématiques)|partitionnés]] selon leurs ordres, on obtient donc<ref>{{Note autre projet|Wikiversité|Introduction à la théorie des nombres/Exercices/Nombres premiers et fonctions arithmétiques#Exercice 1-6|cet exercice corrigé de la leçon « Introduction à la théorie des nombres »|début=Pour plus de détails, voir par exemple}}</ref> :<center><math>\forall n\in\N^*\quad n=\sum_{d|n}\varphi(d)</math>.</center>}}
La [[formule d'inversion de Möbius]] donne alors :<center><math>\forall n\in\N^*\quad\varphi(n)=\sum_{d|n}\mu(d)\frac nd</math>,</center>où {{mvar|μ}} désigne la [[fonction de Möbius]].

==== Applications ====

*La [[cryptologie]] utilise cette fonction. Le chiffrement [[Rivest Shamir Adleman|RSA]] se fonde sur la propriété suivante ([[Théorème d'Euler (arithmétique)|théorème d'Euler]]) :

{{Théorème|titre=[[Théorème d'Euler (arithmétique)|Théorème d'Euler]]|1=Si {{mvar|n}} est un entier strictement positif et {{mvar|a}} un entier premier à {{mvar|n}}, alors {{math|''a''<sup>''φ''(''n'')</sup> ≡ 1}} ([[congruence sur les entiers|modulo]] {{mvar|n}}).}}
* Une autre branche de la [[théorie de l'information]] utilise l'indicatrice : la [[théorie des codes]]. C’est le cas des [[code correcteur|codes correcteurs]], et particulièrement des [[code cyclique|codes cycliques]]. Ce type de code se construit à l'aide d'un [[polynôme cyclotomique]], or<br>Le degré du ''{{Mvar|n}}''-ième polynôme cyclotomique {{math|Φ<sub>''n''</sub>}} est égal à {{math|''φ''(''n'')}}.

=== Théorie analytique des nombres ===
==== Fonctions génératrices ====
Les deux formules {{math|''φ'' {{=}} μ ✻ Id}} et {{math|''φ'' ✻ '''1''' {{=}} Id}}, présentées ci-dessus, où ✻ désigne la [[convolution de Dirichlet]], permettent de calculer respectivement les [[fonction génératrice|fonctions génératrices]] de Dirichlet et de Lambert.

Comme la [[série de Dirichlet]] génératrice de {{math|μ}} est {{math|1/ζ(''s'')}} — où {{math|ζ}} est la [[fonction zêta de Riemann]] — et celle de {{math|Id}} est {{math|ζ(''s'' – 1)}}, [[Convolution de Dirichlet#Séries de Dirichlet|on en déduit]] celle de ''{{math|φ}}'' (qui converge pour {{math|Re(''s'') > 2}}) :<center><math>\sum_{n=1}^{\infty}\frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.</math></center>

La [[série de Lambert]] associée à ''{{math|φ}}'' (qui converge pour |''q''| < 1) est
<center><math>\sum_{n=1}^{\infty}\frac{\varphi(n)q^n}{1-q^n}=\sum_{m=1}^{\infty}mq^m=\frac q{(1-q)^2}.</math></center>

==== Moyenne asymptotique ====
[[Arnold Walfisz]] a établi<ref name=Walfisz>{{Ouvrage|langue=de|prénom1=A.|nom1=Walfisz|titre=Weylsche Exponentialsummen in der neueren Zahlentheorie|lieu=Berlin|éditeur=[[Volkseigener Betrieb|VEB]] [[Deutscher Verlag der Wissenschaften]]|année=1963}}.</ref>

<center><math>\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)</math></center>

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

==== Divisibilité des valeurs de phi par un entier quelconque ====

La propriété qui suit, qui fait partie du « folklore » (c’est-à-dire apparemment dont aucune preuve spécifique n’a été publiée<ref>{{Article|langue=en|prénom1=P.|nom1=Pollack|titre= Two problems on the distribution of Carmichael’s lambda function|périodique= Mathematika|volume=69|date=2023|doi=10.1112/mtk.12222|consulté le=31.12.2023|pages=1195-1220}}</ref>: voir l'introduction de cet article dans laquelle elle est citée comme étant « connue depuis longtemps ») a des conséquences importantes. Par exemple elle exclut la distribution uniforme des valeurs de <math>\varphi(n)</math> dans les progressions arithmétiques modulo <math>q</math> pour n’importe quel entier <math>q>1</math>.

* Pour chaque entier positif <math>q</math>, la relation <math>q|\varphi(n)</math> est vérifiée pour presque tout <math>n</math>, c’est-à-dire à l’exception de  <math>o(x)</math> valeurs de <math>n\le x</math> lorsque <math>x\rightarrow\infty</math>.

Cette propriété est une conséquence élémentaire du fait que la somme des réciproques des premiers congrus à 1 modulo <math>q</math> diverge, qui lui-même est un corollaire de la preuve du [[Théorème de la progression arithmétique]].

== 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 et borne inférieure|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 ''{{Mvar|n}}'' correspondant aux {{Pas clair|date=novembre 2020|valeurs particulièrement petites}} de <math>\frac{\varphi(n)}n</math> sont les ''{{Mvar|n}}'' [[Primorielle|primoriels]], c’est-à-dire ceux qui sont le produit d'un segment initial de la suite de tous les nombres premiers. À partir du [[théorème de Mertens|troisième théorème de Mertens]] et des inégalités de [[Pafnouti Tchebychev|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ù {{math|''o''}} est le [[notation de Landau|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><br />car l'[[ordre multiplicatif]] de {{math|''a''}} modulo {{math|''a{{exp|n}}'' – 1}} vaut {{math|''n''}}.
* <math>\varphi(mn)=\varphi(m)\varphi(n)\frac d{\varphi(d)}\text{ pour }d={\rm pgcd}(m,n),</math><br />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>{{en}} László Tóth, ''Menon's Identity and arithmetical sums representing functions of several variables'', {{arxiv2|1103.5861v2}}, eq. 1.</ref>{{retrait|<math>\sum_{\stackrel{1\le k\le n}{\rm pgcd}(k,n)=1}{\rm pgcd}(k-1,n)=\varphi(n)d(n)</math>}}où {{math|''d''}} est la [[Fonction diviseur#Fonction nombre de diviseurs|fonction nombre de diviseurs]]
{{Démonstration/début|titre=Quelques généralisations de l'identité de Menon}}
B. Sury<ref>Tóth, eq. 5.</ref>
{{retrait|<math>\sum_{\stackrel{1\le k_1, k_2, \dots, k_s\le n}{{\rm pgcd}(k_1,n)=1}}{\rm pgcd}(k_1-1,k_2,\dots,k_s,n)=\varphi(n)\sigma_{s-1}(n)</math>}}
où σ{{ind|''a''}} est la [[Fonction diviseur|fonction somme des puissances ''a''-ièmes des diviseurs]].

N. Rao<ref>Tóth, eq. 3.</ref>
{{retrait|<math>\sum_{\stackrel{1\le k_1, k_2, \dots, k_s\le n}{{\rm pgcd}(k_1,k_2,\dots,k_s,n)=1}}{\rm pgcd}(k_1-a_1,k_2-a_2,\dots,k_s-a_s,n)^s=J_s(n)d(n)</math>}}
où {{math|''a''{{ind|1}}, ''a''{{ind|2}}, … , ''a{{ind|s}}''}} sont des entiers tels que {{math|1=pgcd(''a''{{ind|1}}, ''a''{{ind|2}}, …  , ''a{{ind|s}}'', ''n'') = 1}} et {{math|''J{{ind|s}}''}} est la [[fonction totient de Jordan]].

L. Tóth<ref>Tóth, eq. 35.</ref>
{{retrait|<math>\sum_{\stackrel{1\le k\le m}{{\rm pgcd}(k,m)=1}}{\rm pgcd}(k^2-1,m_1)\gcd(k^2-1,m_2)=\varphi(n)\sum_{\stackrel{d_1\mid m_1} {d_2\mid m_2}} \varphi({\rm pgcd}(d_1, d_2))2^{\omega({\rm ppcm}(d_1, d_2))}</math>}}
où {{math|''m''{{ind|1}}}} et {{math|''m''{{ind|2}}}} sont impairs, {{math|1=''m'' = [[Plus petit commun multiple|ppcm]](''m''{{ind|1}}, ''m''{{ind|2}})}} et ω est la [[Fonction additive (arithmétique)#Exemples de fonctions qui sont seulement additives|fonction nombre de diviseurs premiers distincts]].

En fait, pour toute [[fonction arithmétique]] {{math|''f''}}<ref>Tóth, eq. 2.</ref>{{,}}<ref>Tóth écrit que Menon l'a prouvé en 1965 pour {{math|''f''}} multiplicative, et V. Sita Ramaiah pour {{math|''f''}} quelconque.</ref>,
{{retrait|<math>
\sum_{\stackrel{1\le k\le n}{{\rm pgcd}(k,n)=1}}f({\rm pgcd}(k-1,n))=\varphi(n)\sum_{d\mid n}\frac{(\mu*f)(d)}{\varphi(d)}.
</math>}}
{{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>&nbsp;<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>&nbsp;<ref name=Sitaramachandrarao>{{Article|langue=en|prénom=R.|nom=Sitaramachandrarao|titre=On an error term of Landau II|revue=Rocky Mountain J. Math.|vol=15|année=1985|p.=579-588}}.</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>&nbsp;<ref name=Sitaramachandrarao/><br />({{math||§=''γ''}} est la [[constante d'Euler-Mascheroni|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><br />où [[Fonction additive (arithmétique)#Exemples de fonctions qui sont seulement additives|ω(''{{Mvar|m}}'')]] est le nombre de diviseurs premiers de ''{{Mvar|m}}'' distincts{{refnec|date=décembre 2023}}

== Inégalités ==
Voici quelques [[Inégalité (mathématiques)|inégalités]] impliquant la fonction ''{{math|φ}}'' :
:<math>
\varphi(n) > \frac n{{\rm e}^\gamma\; \log \log n + \frac3{\log \log n}}
</math> pour {{math|''n ''> 2}}<ref>{{Ouvrage|langue=en|nom1={{Lien|Eric Bach}}|lien auteur2=Jeffrey Shallit|prénom2=Jeffrey|nom2=Shallit|titre=Algorithmic Number Theory (Vol I: Efficient Algorithms)|lien éditeur=MIT Press|éditeur=MIT Press|année=1996|isbn=978-0-262-02405-1|url=https://books.google.fr/books?id=iJx1lP9ZcIkC&pg=PA234|passage=234}}.</ref>{{,}}<ref>{{Ouvrage|langue=en|nom=Ribenboim|prénom=Paulo|lien auteur1=Paulo Ribenboim|titre=The New Book of Prime Number Records|numéro d'édition=3|lien éditeur=Springer Science+Business Media|éditeur=Springer|année=1996|isbn=978-0-387-94457-9|passage=320}}.</ref>,

:<math>
\varphi(n) \geqslant \sqrt{\frac n2}
</math> pour {{math|''n ''> 0}}

et
:<math>
\varphi(n) \geqslant \sqrt n
</math> pour {{math|''n ''> 6}}.

On a déjà remarqué que pour {{math|''n''}} premier, {{math|''φ''(''n'') {{=}} ''n ''– 1}}. Pour un [[nombre composé]] {{math|''n''}}, nous avons
{{retrait|<math>
\varphi(n)\leqslant n-\sqrt n.
</math>}}

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

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

Deux inégalités combinant la fonction ''{{math|φ}}'' et la fonction [[somme des diviseurs]] {{math|σ}} sont :

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

== Conjectures ==
Les résultats ci-dessous ne sont encore que des [[conjecture]]s à 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 ===
{{Article détaillé|Nombre nontotient|Nombre hautement totient}}
Un nombre ''totient'' est un nombre entier appartenant à l'[[Image (mathématiques)|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>{{Ouvrage|langue=English|prénom1=Richard K.|nom1=Guy|titre=Unsolved problems in number theory|passage=144|éditeur=Springer-Verlag|collection=Probl. Books Math.|date=2004|isbn=978-0-387-20860-2|lire en ligne=https://zbmath.org/?format=complete&q=an:1058.11001|consulté le=2022-04-18}}</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>{{Ouvrage|langue=English|prénom1=Jozsef|nom1=Sándor|prénom2=Borislav|nom2=Crstici|titre=Handbook of number theory II|passage=230|éditeur=Kluwer Academic Publishers|date=2004|isbn=978-1-4020-2546-4|lire en ligne=https://zbmath.org/?format=complete&q=an:1079.11001|consulté le=2022-04-18}}</ref>, et chaque entier positif a un multiple qui est un nontotient pair<ref>{{Article|langue=en|prénom1=M. Z.|nom1=Zhang|titre=On Nontotients|périodique=Journal of Number Theory|volume=43|numéro=2|date=1993-02-01|issn=0022-314X|doi=10.1006/jnth.1993.1014|lire en ligne=https://www.sciencedirect.com/science/article/pii/S0022314X83710140|consulté le=2022-04-18|pages=168–172}}</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 ===
{{Article détaillé|Nombre noncototient|Nombre hautement cototient}}
La fonction ''cototient'' est définie à partir de l'indicatrice d'Euler, comme {{Math|Id - ''φ''}} : elle associe à tout [[entier naturel]] {{Mvar|n}} non nul le nombre {{math|''n'' – ''φ''(''n'')}}. Ce nombre représente le nombre d'entiers compris entre 1 et {{Mvar|n}} (inclus) et qui ne sont pas [[Nombres premiers entre eux|premiers avec]] {{Mvar|n}} (de manière équivalente, qui ont avec {{mvar|n}} 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 (mathématiques)|image]] de la fonction cototient : c'est-à-dire un entier {{mvar|m}} pour lequel il existe au moins un {{mvar|n}} pour lequel {{math|''n'' – ''φ''(''n'') {{=}} ''m''}}. La ''valence'' ou ''multiplicité'' d'un nombre ''cototient'' {{mvar|m}} 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 {{mvar|m}} n'admettant pas d'[[Antécédent (mathématiques)|antécédent]] par la fonction cototient. De manière équivalente, exprimé algébriquement, ce sont les entiers {{mvar|m}} tels que l'équation {{math|''n'' – ''φ''(''n'') {{=}} ''m''}} 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 {{mvar|m}} tels que l'équation {{math|''n'' – ''φ''(''n'') {{=}} ''m''}} possède plus de solution que chacune des équations {{math|''n'' – ''φ''(''n'') {{=}} ''k''}} pour tout {{math|1 < ''k'' < ''m''}}.

== Notes et références ==
{{Traduction/Référence|lang1=en|art1=Euler's totient function|id1=86973066|lang2=en|art2=Arithmetic function|id2=566776465|type=note}}
{{Références}}

== Articles connexes ==
{{colonnes|nombre=2|
*[[Indicatrice de Carmichael]]
*[[Fonction totient de Jordan]]
*[[Nombre nontotient]]
*[[Nombre hautement totient]]
*[[Nombre noncototient]]
*[[Nombre hautement cototient]]
*[[Théorème de Gauss-Wantzel]]
*[[Théorème de Bateman]]
*[[Liste des sujets nommés d'après Leonhard Euler]]
}}

{{Portail|cryptologie|théorie des nombres}}

[[Catégorie:Arithmétique modulaire]]
[[Catégorie:Leonhard Euler]]
[[Catégorie:Théorie analytique des nombres]]