Indicatrice d'Euler

En théorie des nombres, l'indicateur $\varphi(n)$ d'un entier positif n est défini comme le nombre d'entiers positifs inférieurs ou égaux à n et premiers avec n.

Par exemple, $\varphi(8) = 4$ car les quatre nombres 1, 3, 5 et 7 sont premiers avec 8.

La fonction $\varphi(n)$ ainsi définie est la fonction indicatrice. L'indicateur est généralement appelé l'indicateur Euler ou indicateur d'Euler, après que le mathématicien suisse Leonhard Euler, l'étudia. 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 elle.

La fonction indicatrice est d'une importance majeure car elle donne la taille du groupe multiplicatif des entiers modulo n — plus précisément, la valeur de $\varphi(n)$ est égale à l'ordre du groupe des éléments inversibles de l'anneau $\mathbb{Z}/n\mathbb{Z}$ (voir arithmétique modulaire). Ceci, conjointement avec le théorème de Lagrange, fournit une preuve du théorème d'Euler.

Sommaire

1 Le calcul de la fonction φ d'Euler

2 Autres propriétés

3 Fonction génératrice

4 Croissance de la fonction

5 Quelques valeurs de la fonction φ

6 Voir aussi

Le calcul de la fonction φ d'Euler

Il découle de la définition que $\varphi(1) = 1$ , et $\varphi(n)$ est $(p-1)p^{k-1}\,$ quand n est la kième puissance d'un nombre premier $p^k\,$ . De plus, si m et n sont premiers entre eux alors $\varphi(mn) = \varphi(m) \varphi(n)$ : on dit alors que $\varphi$ est une fonction multiplicative. (schéma de la démonstration : soient A, B, C les ensembles des classes de résidus modulo et premières avec m, n, mn respectivement ; alors il existe une bijection entre AxB et C, par le théorème des restes chinois.) La valeur de $\varphi(n)$ peut aînsi être calculée en utilisant le théorème fondamental de l'arithmétique : si

$n = p_1^{k_1} \ldots p_r^{k_r}$

où les $p_j\,$ sont des nombres premiers distincts, alors

$\varphi(n) = (p_{1}-1)p_{1}^{k_{1}-1} \ldots (p_{r}-1)p_{r}^{k_{r}-1}$

Autres propriétés

Le nombre $\varphi(n)$ est aussi égal au nombre de générateurs du groupe cyclique $C_n\,$ (et par conséquent est aussi le degré du polynôme cyclotomique ( $\Phi_n\,$ ). Comme chaque élément de $C_n\,$ génère un sous-groupe cyclique et que les sous-groupes de $C_n\,$ sont de la forme $C_d\,$ où d divise n (écrit sous la forme $d | n\,$ ), nous obtenons

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

où la somme est étendue à tous les diviseurs positifs d de n.

Nous pouvons maintenant utiliser la formule d'inversion de Möbius pour « inverser » cette somme, nous obtenons une autre formule pour $\varphi(n)$ :

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

où $\mu\,$ est la fonction de Möbius usuelle définie sur l'ensemble des entiers positifs.

Fonction génératrice

Une série de Dirichlet améliorant $\varphi(n)$ est

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

Croissance de la fonction

La croissance de $\varphi(n)$ comme une fonction de n est une question intéressante. La première impression que l'on a pour les petits n est que $\varphi(n)$ doit être notablement plus petit que n est quelque peu erronée. Asymptotiquement, nous avons

$n^{1 - \epsilon} < \varphi(n) < n\,$

pour n'importe quel $\epsilon > 0\,$ et $n > N(\epsilon)\,$ . En fait, si nous considérons

$\frac {\varphi(n)}{n}\,$

nous pouvons écrire, à partir de la formule précédente, sous forme de produit de facteurs

$1 - p^{-1}\,$

où les p sont des nombres premiers divisant n. Par conséquent les valeurs de n correspondantes aux valeurs particulièrement petites du rapport sont les n qui sont le produit d'un segment initial de la suite de tous les nombres premiers. À partir du théorème des nombres premiers il peut être montré qu'une constante ε dans la formule précédente peut par conséquent être remplacée par

$C \log\log \frac {n}{\log n}\,$ .

Quelques valeurs de la fonction φ

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
$\varphi(n)$	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8

$n$	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40
$\varphi(n)$	12	10	22	8	20	12	18	12	28	8	30	16	20	16	24	12	36	18	24	16

$n$	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60
$\varphi(n)$	40	12	42	20	24	22	46	16	42	20	32	24	52	18	40	24	36	28	58	16

$n$	61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80
$\varphi(n)$	60	30	36	32	48	20	66	32	44	24	70	24	72	36	40	36	60	24	78	32