Indicatrice d'Euler

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Les mille premières valeurs de φ(n)

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 l'étude que le mathématicien suisse Leonhard Euler en fit. 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 Calcul
2 Autres propriétés
3 Fonctions génératrices
4 Croissance de la fonction
5 Les 100 premières valeurs de la fonction φ
6 Autres formules impliquant la fonction φ d'Euler
7 Inégalités
8 Conjectures
9 Voir aussi

[modifier] Calcul

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

De la même façon, si les $p i$ désignent les diviseurs de l'entier $n$ , alors:

$\varphi(n) = n \prod_{i}{\left( 1- \frac{1}{p_i} \right) }$

[modifier] Autres propriétés

L'entier $n\,$ est premier si et seulement si $\varphi(n) = n - 1$ .

Si n et m sont premiers entre eux alors $\varphi(n.m) = \varphi(n)\varphi(m)$

Si n est un entier naturel et a est premier avec n, alors d'après le théorème_d'Euler :

$a^{\varphi(n)} \equiv 1 \mod n$

Cette relation est à la base du système de cryptologie RSA.

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.

[modifier] Fonctions génératrices

Les deux fonctions génératices présentées ici sont des conséquences directes du fait que :

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

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

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

qui est dérivé depuis :

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

ou $ζ(s)$ est la Fonction Zeta de Riemann.

Une série de Lambert utilisant $\varphi(n)$ est

$\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}$

qui converge pour |q|<1.

dérivé de :

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

avec

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

[modifier] 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}\,$ .

[modifier] Les 100 premières 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

$n\,$	81	82	83	84	85	86	87	88	89	90	91	92	93	94	95	96	97	98	99	100
$\varphi(n)$	54	40	82	24	64	42	56	40	88	24	72	44	60	46	72	32	96	42	60	40

Avec en gras les nombres premiers $n\,$ et leur indicatrice égale à $n-1\,$ .

[modifier] 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$

$\sum_{k=1}^n\frac{k}{\varphi(k)} = \mathcal{O}(n)$

$\sum_{k=1}^n\frac{1}{\varphi(k)} = \mathcal{O}(\log(n))$

[modifier] Inégalités

Certaines inégalités impliquant la fonction $\varphi$ sont :

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

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

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

Pour un nombre premier n, clairement $\varphi(n) = n-1\,$ . Pour un nombre composé n, nous avons

$\varphi(n) \le n-\sqrt{n}$ (pour un nombre composé n).

Pour tous les $n > 1$ :

$0<\frac{\varphi(n)}{n}<1$

Pour un grand n aléatoire, ces bornes ne peuvent pas être encore améliorées, ou être plus précises :

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

Une paire d'inégalités combinant la fonction $\varphi$ et la fonction diviseur $σ$ sont :

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

[modifier] Conjectures

$n$ est premier si et seulement si $n \equiv 1 \mod \varphi(n)$
$\forall{n > 0}, \exists{m \neq n}, \varphi(n)=\varphi(m)$ (énoncée par Robert Daniel Carmichaël)