TotientFunction

L'indicatrice d'Euler est une fonction de la théorie des nombres.

En mathématique pure, elle intervient à la fois en théorie des groupes, en théorie algébrique des nombres et en théorie analytique des nombres.

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.

Définition

 l'indicateur d'Euler φ est la fonction de l'ensemble ℕ* des entiers strictement positifs dans lui-même qui à n associe le nombre d'entiers strictement positifs inférieurs ou égaux à n et premiers avec n.

Plus formellement,  

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

par exemple : 

Calcul de la valeur de l'indicatrice d'Euler 

La valeur de l'indicatrice d'Euler s'obtient par l'expression de n donnée par le théorème fondamental de l'arithmétique :

\mathrm{Si}\quad  n=\prod_{i=1}^q p_i^{k_i}\quad \mathrm{alors} \quad \varphi (n)=\prod_{i=1}^q (p_i-1) p_i^{k_i-1} = n \prod_{i=1}^q {\left( 1- \frac{1}{p_i} \right) }

Dans la formulepi désigne un nombre premier et ki un entier strictement positif.

En effet, le caractère multiplicatif de l'indicatrice d'Euler et une récurrence montrent que :

\varphi(n) = \prod_{i=1}^q \varphi(p_i^{k_i})

Il suffit alors de dénombrer le nombre d'entiers non premiers avec une puissance d'un nombre premier et plus petit que celui-ci pour remarquer que :

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

Ce qui permet de conclure la démonstration.

Applications

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.



 phi(p)=p-1,
(1)

D'autres formules impliquant la fonction d'Euler : 

phi(p^alpha)=p^alpha-p^(alpha-1)
(2)
=p^(alpha-1)(p-1)
(3)
=p^alpha(1-1/p).
(4)

Pour m divisible par p et phi_p(m) le nombre d'entiers positifs <=m non divisibles par p. Comme vu précédemment,, p, 2p, ..., (m/p)p ont des facteurs communs, donc 

phi_p(m)=m-m/p
(5)
=m(1-1/p).
(6)

Pour q un autre nombre premier divisant m. Les entiers divisibles par  q sont q, 2q, ..., (m/q)q. Le nombre de termes qui doit être soustrait de phi_p pour obtenir phi_(pq) est

Deltaphi_q(m)=m/q-m/(pq)
(7)
=m/q(1-1/p),
(8)

et

phi_(pq)(m)=phi_p(m)-Deltaphi_q(m)
(9)
=m(1-1/p)-m/q(1-1/p)
(10)
=m(1-1/p)(1-1/q).
(11)

Le cas général est donc 

phi(n)=nproduct_(p|n)(1-1/p)
(12)
=n(1-1/(p_1))(1-1/(p_2))...(1-1/(p_r)),
(13)

Une autre formule intéressante lie phi(n^k) et phi(n)

 phi(n^k)=n^(k-1)phi(n)
(14)

(A. Olofsson, Déc. 30, 2004).

Une autre formule lie les diviseurs d de n à n :

 sum_(d|n)phi(d)=n.
(15)

La fonction indicatrice est définie par la formule d'inversion de Möbius dans la formule qui suit : 

 sum_(d)dmu(n/d)=phi(n),
(16)

où  mu(n) est la fonction de Möbius définie sur l'ensemble des entiers strictement positifs.

Une série de Dirichlet utilisant  \varphi(n) est : 

 sum_(n=1)^infty(phi(n))/(n^s)=(zeta(s-1))/(zeta(s))
(17)

pour s>2 (Hardy et Wright 1979).

La fonction indicatrice satisfait aussi l'inégalité : 

 phi(n)>=sqrt(n)
(18)

pour tout n à l'exception de n=2 et n=6 (Kendall et Osborn 1965; Mitrinović et Sándor 1995). Par conséquent, les seules valeurs de  n pour lesquelles phi(n)=2 sont n=3, 4, et 6. De plus, 

 phi(n)<=n-sqrt(n)
(19)

(Sierpiński etSchinzel 1988; Mitrinović et Sándor 1995).

TotientFunctionInequality

phi(n)  satisfait aussi

 lim inf_(n->infty)phi(n)(lnlnn)/n=e^(-gamma),
(20)

gamma est la constante d'Euler-Mascheroni. Les valeurs de n pour lesquelles phi(n)<e^(-gamma)n/(lnlnn) sont 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 22, ... (Sloane's A100966).

La fonction diviseur satisfait à la congruence

nsigma(n)=2 (mod phi(n))
(21)
=
={0 (mod phi(n)) if phi(n)=2; 2 (mod phi(n)) otherwise
(22)

pour tous les nombres premiers p>=5 and aucun nombre composé à l'exception de 4, 6, et 22, où sigma(n) est la fonction diviseur. Ceci a été prouvé par Subbarao (1974). A ce jour, on ne connait pas la solution de

 n-1=0 (mod phi(n))
(23)

(Honsberger 1976, p. 35).

Un corollaire du théorème de Zsigmondy mène à la formule suivante : 

 phi(a^n+b^n)=0 (mod n)
(24)

(Zsigmondy 1882, Moree 2004, Ruiz 2004ab).

Les premiers n pour lesquels on a :

 phi(n)=phi(n+1)
(25)

sont  1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (Sloane's A001274), qui ont pour valeurs communes phi(n)=1, 2, 8, 48, 80, 96, 128, 240, 288, 480, ... (Sloane's A003275).

Le seul n<10^(10) pour lequel

 phi(n)=phi(n+1)=phi(n+2)
(26)

est n=5186, étant donné

 phi(5186)=phi(5187)=phi(5188)=2^53^4
(27)

(Guy 2004).

Les valeurs de phi(n) qui sont proches les unes des autres incluent

phi(25930)=phi(25935)=phi(25940)=phi(25942)
(28)
=2^73^4
(29)
phi(404471)=phi(404473)=phi(404477)
(30)
=2^83^25^27
(31)

(Guy 2004, p. 139). McCranie a trouvé une suite arithmétique de 6 nombres avec les fonctions indicatrices d'Euleur égales

 phi(583200)=phi(583230)=phi(583260)=phi(583290) 
 =phi(583320)=phi(583350)=155520,
(32)

ainsi que d'autres suites de 6 nombres commençant par 1166400, 1749600, ... (Sloane's A050518).

Si la supposition de Goldbach est vraie, alors pour chaque entier positif m, il existe des nombres premiers p et q tels que

 phi(p)+phi(q)=2m
(33)

(Guy 2004). 

Guy (2004) a étudié les solutions de

 phi(sigma(n))=n,
(34)

F. Helenius a trouvé 365 solutions, les premières étant 2, 8, 12, 128, 240, 720, 6912, 32768, 142560, 712800, ... (Sloane's A001229).