Indicatrice d'Euler

Les mille premières valeurs de φ(n)

En mathématiques, l'indicatrice d'Euler est une fonction 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 (1707 - 1783) qui fut le premier à l'étudier.

Définition et calcul explicite

Définition et exemple

• 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 :

• φ(8) = 4 car parmi les nombres de 1 à 8, seuls les quatre nombres 1, 3, 5 et 7 sont premiers avec 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 m ≤ n par m < n dans la définition ci-dessus de φ(n)).
• φ(2) = 1.

Premières propriétés

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 au nombre de générateurs d'un groupe cyclique d'ordre n.

Cette propriété est démontrée dans le paragraphe Structure additive de l'article Anneau Z/nZ.

• 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.

• Si u et v sont deux entiers strictement positifs et premiers entre eux, alors φ(u.v)=φ(u).φ(v).

Une telle fonction est dite multiplicative. On peut démontrer cette propriété à partir 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 d'éléments générateurs du groupe produit est donc égal à φ(u).φ(v). L'isomorphisme montre que cette valeur est égale au nombre d'éléments générateurs du groupe Z/(uv)Z, ce qui démontre la formule recherchée.

Calcul

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 formule, p_i désigne un nombre premier et k_i 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.

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.

• Un entier p > 0 est premier si et seulement si φ(p) = p - 1.

Cette propriété est une conséquence directe du calcul explicite de l'indicatrice.

La cryptologie utilise largement cette fonction. Le code RSA se fonde sur le théorème d'Euler, indiquant que si n est un entier strictement positif et a un entier premier avec n, alors a^φ(n) ≡ 1 (mod 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 de polynôme cyclotomique et le degré du polynôme cyclotomique Φ_n d'indice n à coefficients dans les entiers est égal à φ(n). Plus précisément, on dispose des égalités suivantes :

$X^n-1 \ = \ \prod_{d\mid n} \Phi_d (X) \quad \mathrm{et} \ \mathrm{donc} \quad \sum_{d\mid n}\varphi(d)=n$

La somme et le produit sont étendus à tous les diviseurs positifs d de n.

La formule d'inversion de Möbius permet d'inverser cette somme :

$\varphi(n)=\sum_{d\mid n} d \mu(n/d)$

Ici, μ désigne la fonction de Möbius usuelle définie sur l'ensemble des entiers strictement positifs, la démonstration est proposée dans l'article associé.

Théorie analytique des nombres

Fonctions génératrices

Les deux fonctions génératrices présentées ici se calculent à l'aide de

$\sum_{d|n} \varphi(d) = n.$

La série de Dirichlet associée à $\varphi(n)$ satisfait

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

lorsque $\Re s>2$, ce qui suit de

$\zeta(s) \sum_{n=1}^\infty \frac{\varphi(n)}{n^s} = \sum_{n=1}^\infty \left(\sum_{d|n} \varphi(d)\right) \frac{1}{n^s} = \sum_{n=1}^\infty \frac{n}{n^s} = \zeta(s-1),$

où $\zeta(s)$ est la fonction zêta de Riemann.

La série de Lambert associée à $\varphi(n)$ satisfait (pour |q|<1)

$\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}=\sum_{n=1}^{\infty} \varphi(n) \sum_{r\ge 1} q^{rn}= \sum_{k\ge 1} q^k \sum_{n|k} \varphi(n) = \sum_{k\ge 1} k q^k=\frac{q}{(1-q)^2}.$

Moyenne asymptotique

Arnold Walfisz (en) a établi

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

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

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 il peut être montré que l'estimation ci-dessus peut être remplacée par

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

et que la minoration est optimale.

Les 99 premières valeurs de la fonction φ

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

On observe que, excepté pour n = 1 ou 2, $\varphi(n)$ est pair, propriété qui est générale. En effet, en notant $n=2^k \prod_{i=1}^q p_i^{k_i}$ avec les $p_i$ impairs et q éventuellement nul (produit vide), on a :

$\varphi (n)=2^{k - 1} \prod_{i=1}^q (p_i-1) p_i^{k_i-1}$

Or si n > 2, alors k > 1 ou q > 0. Dans un cas comme dans l'autre, on obtient bien que $\varphi(n)$ est pair.

Autres formules impliquant la fonction φ d'Euler

$\;\varphi(n^m) = n^{m-1}\varphi(n)$ pour $m\ge 1$

$\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}$

$\sum_{1\le k\le n \atop (k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)$ pour $\;n>1$

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

• $\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+\mathcal{O}\left((\log n)^{2/3}(\log\log n)^{4/3}\right)$ 

• $\sum_{k=1}^n\frac{k}{\varphi(k)} = \frac{315\zeta(3)}{2\pi^4}n-\frac{\log n}2+\mathcal{O}\left((\log n)^{2/3}\right)$  

• $\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)+\mathcal{O}\left(\frac{(\log n)^{2/3}}n\right)$

(ici γ est la constante d'Euler).

Inégalités

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

$\varphi(n) > \frac n{e^\gamma\; \log \log n + \frac3{\log \log n}}$ pour n > 2, où γ est la constante d'Euler,

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

et

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

Pour un nombre premier n, clairement φ(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 ne peuvent pas être améliorées, en effet :

$\liminf\frac{\varphi(n)}n=0\mbox{ et }\limsup\frac{\varphi(n)}n=1.$

Deux inégalités combinant la fonction φ et la fonction diviseur σ sont :

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

Conjectures

• $n$ est premier si et seulement si $n \equiv 1 \mod \varphi(n)$ (énoncée par Derrick Henry Lehmer)
• $\forall{n > 0}, \exists{m \neq n}, \varphi(n)=\varphi(m)$ (c'est la « conjecture de Carmichael (en) » que Robert Daniel Carmichael, en 1907, a énoncée et cru démontrer, mais qui reste toujours un problème ouvert).

Voir aussi

• Anti-indicateur
• Anticoïndicateur
• Problème de Lehmer

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Euler's totient function » (voir la liste des auteurs)