Indicatrice d'Euler

Cet article est une débauche. Vous pouvez m’aider à l'améliorer.

« Fonction phi d'Euler » redirige ici. Ne pas confondre avec Fonction d'Euler.

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, 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 $\varphi$ (ou $\phi$ ) 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^[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)$ . De nos jours, on emploie la lettre grecque phi minuscule en italique $ϕ$ ou $φ$ .
En 1879, J. J. Sylvester invente le terme de totient pour désigner cette fonction^[4], de sorte qu'elle est généralement désignée sous le terme de « 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 $φ$ , de l'ensemble ℕ^* des entiers strictement positifs dans lui-même, définie par :
${\begin{array}{ccccl}\varphi &:&\mathbb {N} ^{*}&\longrightarrow &\mathbb {N} ^{*}\\&&n&\longmapsto &\mathrm {card} (\{m\in \mathbb {N} ^{*}~|~m\leqslant n~{\text{et}}~m~\mathrm {premier~avec} ~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 avec 8 ;

$φ (12) = 4$ 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$ , c.-à-d. si et seulement si $φ (p) = p - 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 $n$ > 1, on peut remplacer non seulement $m$ ∈ ℕ* par $m$ ∈ ℕ mais $m \leq 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 A000010 de l'OEIS).
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

Premières propriétés

Les $\varphi (11)/2=5$ hendécagones réguliers (à 11 sommets)

Théorème^[5] —

Pour tout entier $n$ strictement positif, $φ (n)$ est égal :
au nombre d'éléments inversibles de l'anneau ℤ/nℤ ;

au nombre de générateurs d'un groupe cyclique d'ordre n.

au nombre de racines n-ièmes de l'unité qui sont primitives.

pour n supérieur ou égal à trois, au double du nombre de polygones réguliers croisés ou non à n sommets (ou côtés).

La fonction $φ$ est multiplicative, c'est-à-dire que si u et v sont deux entiers strictement positifs premiers entre eux, alors $φ$ (uv) = $φ$ (u) $φ$ (v).

Calcul

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}^{r}p_{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-{\frac {1}{p_{i}}}\right)}$
où chaque $p$ _i désigne un nombre premier et $k$ _i un entier strictement positif : on peut le déduire du théorème précédent^[5] ou, plus élémentairement, du principe d'inclusion-exclusion.
Par exemple, pour les nombres sans facteurs carré $n=\prod _{i=1}^{r}p_{i}$ , comme par exemple les primorielles, on obtient $\quad \varphi (n)=\prod _{i=1}^{r}(p_{i}-1)$ .

Algorithme de calcul

En 2023, on ne connaît 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.

Transformée de Fourier

L'indicatrice d'Euler est la transformée de Fourier discrète du PGCD, évaluée en 1^[6].
Soit

${\mathcal {F}}\{\mathbf {x} \}[m]=\sum \limits _{k=1}^{n}x_{k}\cdot \mathrm {e} ^{-2\mathrm {i} \pi {\frac {mk}{n}}}$

où $x k = PGCD(k, n)$ pour $k \in {1, ..., n}$ . Alors

$\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}}}.$

La partie réelle de la formule est

$\varphi (n)=\sum \limits _{k=1}^{n}\mathrm {PGCD} (k,n)\cos \left({\frac {2\pi k}{n}}\right).$

Par exemple, en utilisant $\cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}$ et $\cos {\tfrac {2\pi }{5}}={\tfrac {{\sqrt {5}}-1}{4}}$ : ${\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 {{\sqrt {5}}+1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+5\cdot (-1)\\&&+\ 2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+10\cdot (1)\\&=&4.\end{array}}$
Contrairement au produit d'Euler et la formule de la somme des diviseurs, Celle-ci ne requiert pas de connaître les facteurs de $n$ . Cependant, elle implique le calcul du PGCD de $n$ et de tous les entiers positifs inférieurs à $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.

Si $a$ divise $b$ alors $φ (a)$ divise $φ (b)$ .

Si $n$ a $q$ diviseurs premiers impairs distincts, $φ (n)$ est divisible par $2 q$ .

Ces deux 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 φ (n) / 2$ .

En effet, $m \mapsto 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$ .

Dans le groupe $(ℤ/ n ℤ, +)$ , les éléments d'ordre $d$ (un diviseur de $n$ ) sont les générateurs du sous-groupe engendré par $n / d$ . Si les éléments de $ℤ/ n ℤ$ sont partitionnés selon leurs ordres, on obtient donc^[7] :
$\forall n\in \mathbb {N} ^{*}\quad n=\sum _{d|n}\varphi (d)$ .
La formule d'inversion de Möbius donne alors :
$\forall n\in \mathbb {N} ^{*}\quad \varphi (n)=\sum _{d|n}\mu (d){\frac {n}{d}}$ ,
où $μ$ 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) :

Théorème — Si $n$ est un entier strictement positif et $a$ un entier premier à $n$ , alors $a φ (n) \equiv 1$ (modulo $n$ ).

Une autre branche de la théorie de l'information utilise l'indicatrice : la théorie des codes. C’est le 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 $n$ -ième polynôme cyclotomique $Φ n$ est égal à $φ (n)$ .

Théorie analytique des nombres

Fonctions génératrices

Les deux formules $φ = μ ✻ Id$ et $φ ✻ 1 = Id$ , 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 $μ$ 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

Arnold Walfisz a établi^[8]
$\sum _{n\leq x}\varphi (n)={\frac {3}{\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. À 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^[9]: 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 $\varphi (n)$ dans les progressions arithmétiques modulo $q$ pour n’importe quel entier $q>1$ .

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

Cette propriété est une conséquence élémentaire du fait que la somme des réciproques des premiers congrus à 1 modulo $q$ 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

$n^{1-\varepsilon }<\varphi (n)\leqslant n-1\$

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

${\frac {\varphi (n)}{n}}=\prod _{p|n,\ p{\text{ premier}}}(1-p^{-1})\,$

on peut constater que les valeurs de $n$ correspondant aux valeurs particulièrement petites^[pas clair] de ${\frac {\varphi (n)}{n}}$ 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

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

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

Autres formules impliquant la fonction φ d'Euler

$\forall n>0,\ \forall a>1\quad n|\varphi (a^{n}-1)$
car l'ordre multiplicatif de $a$ modulo $a n - 1$ vaut $n$ .

$\varphi (mn)=\varphi (m)\varphi (n){\frac {d}{\varphi (d)}}{\text{ pour }}d={\rm {pgcd}}(m,n),$
en particulier :
$\varphi (2m)={\begin{cases}2\varphi (m)&{\text{ si }}m{\text{ est pair}}\\\varphi (m)&{\text{ si }}m{\text{ est impair}}\end{cases}}$

$\forall k\geq 1\quad \varphi (n^{k})=n^{k-1}\varphi (n).$

$\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}.$

$\forall n>1\quad \sum _{1\leq k\leq n \atop {\rm {pgcd}}(k,n)=1}k={\frac {1}{2}}n\varphi (n).$

$\sum _{k=1}^{n}\varphi (k)={\frac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right).$

En 1965, P. Kesava Menon a démontré^[10] $\sum _{{\stackrel {1\leq k\leq n}{\rm {pgcd}}}(k,n)=1}{\rm {pgcd}}(k-1,n)=\varphi (n)d(n)$ où $d$ est la fonction nombre de diviseurs
Quelques généralisations de l'identité de Menon
B. Sury^[11] $\sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq n}{{\rm {pgcd}}(k_{1},n)=1}}{\rm {pgcd}}(k_{1}-1,k_{2},\dots ,k_{s},n)=\varphi (n)\sigma _{s-1}(n)$ où σ_a est la fonction somme des puissances a-ièmes des diviseurs.
N. Rao^[12]
$\sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq 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)$
 
   
     
       
         ∑
         
           
             
               
                 
                   
                     p
                     g
                     c
                     d
                   
                 
                 (
                 
                   k
                   
                     1
                   
                 
                 ,
                 
                   k
                   
                     2
                   
                 
                 ,
                 …
                 ,
                 
                   k
                   
                     s
                   
                 
                 ,
                 n
                 )
                 =
                 1
               
               
                 1
                 ≤
                 
                   k
                   
                     1
                   
                 
                 ,
                 
                   k
                   
                     2
                   
                 
                 ,
                 …
                 ,
                 
                   k
                   
                     s
                   
                 
                 ≤
                 n
               
             
           
         
       
       
         
           p
           g
           c
           d
         
       
       (
       
         k
         
           1
         
       
       −
       
         a
         
           1
         
       
       ,
       
         k
         
           2
         
       
       −
       
         a
         
           2
         
       
       ,
       …
       ,
       
         k
         
           s
         
       
       −
       
         a
         
           s
         
       
       ,
       n
       
         )
         
           s
         
       
       =
       
         J
         
           s
         
       
       (
       n
       )
       d
       (
       n
       )
     
   
   {\displaystyle \sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq 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)}
 
$\sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq 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)$ où $a 1, a 2, \dots , a s$ sont des entiers tels que $pgcd(a 1, a 2, \dots , a s, n) = 1$ et $J s$ est la fonction totient de Jordan.

L. Tóth^[13]
$\sum _{\stackrel {1\leq k\leq 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}))}$
 
   
     
       
         ∑
         
           
             
               
                 
                   
                     p
                     g
                     c
                     d
                   
                 
                 (
                 k
                 ,
                 m
                 )
                 =
                 1
               
               
                 1
                 ≤
                 k
                 ≤
                 m
               
             
           
         
       
       
         
           p
           g
           c
           d
         
       
       (
       
         k
         
           2
         
       
       −
       1
       ,
       
         m
         
           1
         
       
       )
       gcd
       (
       
         k
         
           2
         
       
       −
       1
       ,
       
         m
         
           2
         
       
       )
       =
       φ
       (
       n
       )
       
         ∑
         
           
             
               
                 
                   d
                   
                     2
                   
                 
                 ∣
                 
                   m
                   
                     2
                   
                 
               
               
                 
                   d
                   
                     1
                   
                 
                 ∣
                 
                   m
                   
                     1
                   
                 
               
             
           
         
       
       φ
       (
       
         
           p
           g
           c
           d
         
       
       (
       
         d
         
           1
         
       
       ,
       
         d
         
           2
         
       
       )
       )
       
         2
         
           ω
           (
           
             
               p
               p
               c
               m
             
           
           (
           
             d
             
               1
             
           
           ,
           
             d
             
               2
             
           
           )
           )
         
       
     
   
   {\displaystyle \sum _{\stackrel {1\leq k\leq 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}))}}
 
$\sum _{\stackrel {1\leq k\leq 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}))}$ où $m 1$ et $m 2$ sont impairs, $m = ppcm (m 1, m 2)$ et ω est la fonction nombre de diviseurs premiers distincts.

En fait, pour toute fonction arithmétique $f$ ^[14]^,^[15],
$\sum _{\stackrel {1\leq k\leq n}{{\rm {pgcd}}(k,n)=1}}f({\rm {pgcd}}(k-1,n))=\varphi (n)\sum _{d\mid n}{\frac {(\mu *f)(d)}{\varphi (d)}}.$
 
   
     
       
         ∑
         
           
             
               
                 
                   
                     p
                     g
                     c
                     d
                   
                 
                 (
                 k
                 ,
                 n
                 )
                 =
                 1
               
               
                 1
                 ≤
                 k
                 ≤
                 n
               
             
           
         
       
       f
       (
       
         
           p
           g
           c
           d
         
       
       (
       k
       −
       1
       ,
       n
       )
       )
       =
       φ
       (
       n
       )
       
         ∑
         
           d
           ∣
           n
         
       
       
         
           
             (
             μ
             ∗
             f
             )
             (
             d
             )
           
           
             φ
             (
             d
             )
           
         
       
       .
     
   
   {\displaystyle \sum _{\stackrel {1\leq k\leq n}{{\rm {pgcd}}(k,n)=1}}f({\rm {pgcd}}(k-1,n))=\varphi (n)\sum _{d\mid n}{\frac {(\mu *f)(d)}{\varphi (d)}}.}
 
$\sum _{\stackrel {1\leq k\leq n}{{\rm {pgcd}}(k,n)=1}}f({\rm {pgcd}}(k-1,n))=\varphi (n)\sum _{d\mid n}{\frac {(\mu *f)(d)}{\varphi (d)}}.$
$\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{2/3}(\log \log n)^{4/3}\right)$ ^[8].

$\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)$ ^[16].

$\sum _{k=1}^{n}{\frac {1}{\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)$ ^[16]
( $γ$ est la constante d'Euler).

$\forall m>1\quad \sum _{1\leq k\leq n \atop {\rm {pgcd}}(k,m)=1}1=n{\frac {\varphi (m)}{m}}+O\left(2^{\omega (m)}\right)$
où ω( $m$ ) est le nombre de diviseurs premiers de $m$ distincts^{[réf. nécessaire]}

Inégalités

Voici quelques inégalités impliquant la fonction $φ$ :

$\varphi (n)>{\frac {n}{{\rm {e}}^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}$ pour $n > 2$ ^[17]^,^[18],

$\varphi (n)\geqslant {\sqrt {\frac {n}{2}}}$ pour $n > 0$

et

$\varphi (n)\geqslant {\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)\leqslant n-{\sqrt {n}}.$
Par conséquent, pour tout $n > 1$ :
$0<{\frac {\varphi (n)}{n}}<1.$
 
   
     
       0
       <
       
         
           
             φ
             (
             n
             )
           
           n
         
       
       <
       1.
     
   
   {\displaystyle 0<{\frac {\varphi (n)}{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.$
 
   
     
       
         
           
             6
             
               n
               
                 2
               
             
           
           
             π
             
               2
             
           
         
       
       <
       φ
       (
       n
       )
       σ
       (
       n
       )
       <
       
         n
         
           2
         
       
       
         
            pour 
         
       
       n
       >
       1.
     
   
   {\displaystyle {\frac {6n^{2}}{\pi ^{2}}}<\varphi (n)\sigma (n)<n^{2}{\mbox{ pour }}n>1.}
 
Conjectures

Les résultats ci-dessous ne sont encore que des conjectures à l'heure actuelle :

$n$ est premier si (et seulement si) $n\equiv 1{\bmod {\varphi }}(n)$ (c'est le problème de Lehmer, énoncé par Derrick Lehmer)

$\forall {n>0}\quad \exists {m\neq n}\quad \varphi (n)=\varphi (m)$ (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

Articles détaillés : Nombre nontotient et Nombre hautement totient.

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^[19].
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^[20], et chaque entier positif a un multiple qui est un nontotient pair^[21].
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

Articles détaillés : Nombre noncototient et Nombre hautement cototient.

La fonction cototient est définie à partir de l'indicatrice d'Euler, comme $Id - φ$ : elle associe à tout entier naturel $n$ non nul le nombre $n - φ (n)$ . Ce nombre représente le nombre d'entiers compris entre 1 et $n$ (inclus) et qui ne sont pas premiers avec $n$ (de manière équivalente, qui ont avec $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 de la fonction cototient : c'est-à-dire un entier $m$ pour lequel il existe au moins un $n$ pour lequel $n - φ (n) = m$ . La valence ou multiplicité d'un nombre cototient $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 $m$ n'admettant pas d'antécédent par la fonction cototient. De manière équivalente, exprimé algébriquement, ce sont les entiers $m$ tels que l'équation $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 $m$ tels que l'équation $n - φ (n) = m$ possède plus de solution que chacune des équations $n - φ (n) = k$ pour tout $1 < k < m$ .

Notes et références

(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 « Arithmetic function » (voir la liste des auteurs).

↑ (la) L. Euler, « Theoremata arithmetica nova methodo demonstrata », Novi Commentarii academiae scientiarum Petropolitanae, vol. 8,‎ 1763, p. 74-104 (lire en ligne), ou Opera Omnia, Series 1, vol. 2, p. 531-555. 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.

↑ (la) L. Euler, « Speculationes circa quasdam insignes proprietates numerorum », Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4,‎ 1784, p. 18-30 (lire en ligne), 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.

↑ (la) Carl Friedrich Gauss, Disquisitiones arithmeticae (lire en ligne).

↑ (en) James Joseph Sylvester, American Journal of Mathematics, Johns Hopkins University Press, 1879 (lire en ligne), « On certain ternary cubic-form equations », p. 361

↑ ^{a et b} Pour une démonstration, voir par exemple « Fonctions arithmétiques », dans la leçon « Introduction à la théorie des nombres » sur Wikiversité.

↑ (en) Wolfgang Schramm, « The Fourier transform of functions of the greatest common divisor », Electronic Journal of Combinatorial Number Theory, vol. A50, n^o 8(1),‎ 2008 (lire en ligne)

↑ Pour plus de détails, voir par exemple cet exercice corrigé de la leçon « Introduction à la théorie des nombres » sur Wikiversité.

↑ ^{a et b} (de) A. Walfisz, Weylsche Exponentialsummen in der neueren Zahlentheorie, Berlin, VEB Deutscher Verlag der Wissenschaften, 1963.

↑ (en) P. Pollack, « Two problems on the distribution of Carmichael’s lambda function », Mathematika, vol. 69,‎ 2023, p. 1195-1220 (DOI 10.1112/mtk.12222)

↑ (en) László Tóth, Menon's Identity and arithmetical sums representing functions of several variables, arXiv:1103.5861v2, eq. 1.

↑ Tóth, eq. 5.

↑ Tóth, eq. 3.

↑ Tóth, eq. 35.

↑ Tóth, eq. 2.

↑ Tóth écrit que Menon l'a prouvé en 1965 pour $f$ multiplicative, et V. Sita Ramaiah pour $f$ quelconque.

↑ ^{a et b} (en) R. Sitaramachandrarao, « On an error term of Landau II », Rocky Mountain J. Math., vol. 15,‎ 1985, p. 579-588.

↑ (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.

↑ (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, 3^e éd. (ISBN 978-0-387-94457-9), p. 320.

↑ (en) Richard K. Guy, Unsolved problems in number theory, Springer-Verlag, coll. « Probl. Books Math. », 2004 (ISBN 978-0-387-20860-2, lire en ligne), p. 144

↑ (en) Jozsef Sándor et Borislav Crstici, Handbook of number theory II, Kluwer Academic Publishers, 2004 (ISBN 978-1-4020-2546-4, lire en ligne), p. 230

↑ (en) M. Z. Zhang, « On Nontotients », Journal of Number Theory, vol. 43, n^o 2,‎ 1^er février 1993, p. 168–172 (ISSN 0022-314X, DOI 10.1006/jnth.1993.1014, lire en ligne, consulté le 18 avril 2022)

Articles connexes

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 de la cryptologie

Arithmétique et théorie des nombres
<footer>source wp:Indicatrice d'Euler</footer>

[1] (la) L. Euler, « Theoremata arithmetica nova methodo demonstrata », Novi Commentarii academiae scientiarum Petropolitanae, vol. 8,‎ 1763, p. 74-104 (lire en ligne), ou Opera Omnia, Series 1, vol. 2, p. 531-555. 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.

[2] (la) L. Euler, « Speculationes circa quasdam insignes proprietates numerorum », Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4,‎ 1784, p. 18-30 (lire en ligne), 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.

[3] (la) Carl Friedrich Gauss, Disquisitiones arithmeticae (lire en ligne).

[4] (en) James Joseph Sylvester, American Journal of Mathematics, Johns Hopkins University Press, 1879 (lire en ligne), « On certain ternary cubic-form equations », p. 361

[Wikiversité-5] {a et b} Pour une démonstration, voir par exemple « Fonctions arithmétiques », dans la leçon « Introduction à la théorie des nombres » sur Wikiversité.

[6] (en) Wolfgang Schramm, « The Fourier transform of functions of the greatest common divisor », Electronic Journal of Combinatorial Number Theory, vol. A50, n^o 8(1),‎ 2008 (lire en ligne)

[7] Pour plus de détails, voir par exemple cet exercice corrigé de la leçon « Introduction à la théorie des nombres » sur Wikiversité.

[Walfisz-8] {a et b} (de) A. Walfisz, Weylsche Exponentialsummen in der neueren Zahlentheorie, Berlin, VEB Deutscher Verlag der Wissenschaften, 1963.

[9] (en) P. Pollack, « Two problems on the distribution of Carmichael’s lambda function », Mathematika, vol. 69,‎ 2023, p. 1195-1220 (DOI 10.1112/mtk.12222)

[10] (en) László Tóth, Menon's Identity and arithmetical sums representing functions of several variables, arXiv:1103.5861v2, eq. 1.

[11] Tóth, eq. 5.

[12] Tóth, eq. 3.

[13] Tóth, eq. 35.

[14] Tóth, eq. 2.

[15] Tóth écrit que Menon l'a prouvé en 1965 pour $f$ multiplicative, et V. Sita Ramaiah pour $f$ quelconque.

[Sitaramachandrarao-16] {a et b} (en) R. Sitaramachandrarao, « On an error term of Landau II », Rocky Mountain J. Math., vol. 15,‎ 1985, p. 579-588.

[17] (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.

[18] (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, 3^e éd. (ISBN 978-0-387-94457-9), p. 320.

[19] (en) Richard K. Guy, Unsolved problems in number theory, Springer-Verlag, coll. « Probl. Books Math. », 2004 (ISBN 978-0-387-20860-2, lire en ligne), p. 144

[20] (en) Jozsef Sándor et Borislav Crstici, Handbook of number theory II, Kluwer Academic Publishers, 2004 (ISBN 978-1-4020-2546-4, lire en ligne), p. 230

[21] (en) M. Z. Zhang, « On Nontotients », Journal of Number Theory, vol. 43, n^o 2,‎ 1^er février 1993, p. 168–172 (ISSN 0022-314X, DOI 10.1006/jnth.1993.1014, lire en ligne, consulté le 18 avril 2022)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

$\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

$\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

Indicatrice d'Euler

De Mi caja de notas

Histoire et notation

Définition et exemples

Premières propriétés

Calcul

Algorithme de calcul

Transformée de Fourier

Autres propriétés

Arithmétique modulaire

Applications

Théorie analytique des nombres

Fonctions génératrices

Moyenne asymptotique

Divisibilité des valeurs de phi par un entier quelconque

Croissance de la fonction

Autres formules impliquant la fonction φ d'Euler

Inégalités

Conjectures

Nombres remarquables

Fonction indicatrice

Fonction cototient

Notes et références

Articles connexes

$\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