Fonction phi d'Euler

Fonction phi d'Euler

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 est utilisée pour les 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.

Sommaire

Définition et calcul explicite

Définition et exemple

  • L'indicatrice d'Euler φ est la fonction de l'ensemble des entiers strictement positifs dans lui-même, qui à n associe le nombre d'entiers positifs inférieurs à n et premiers avec n.

n n'étant jamais premier avec lui-même, il ne sert à rien de le compter dans la définition, excepté φ(1)=1.

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

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 d'éléments primitifs d'un groupe cyclique d'ordre n.

Un élément primitif désigne un membre du groupe engendrant le groupe entier. Cette propriété est démontrée dans le paragraphe Théorème fondamental de l'article Groupe cyclique.

Le groupe des unités désigne l'ensemble des éléments inversibles pour la multiplication de l'anneau. 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. Cette propriété est une conséquence du théorème des restes chinois. En effet, soit G d'ordre u.v, et Gu et Gv d'ordres respectifs u et v. Le théorème chinois montre que G est isomorphe à GuxGv. Un élément du groupe produit est générateur si et seulement si sa première composante est génératrice du premier groupe et sa deuxième composante est génératrice du deuxième groupe. 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 G, 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}{\left( 1- \frac{1}{p_i} \right) }

Dans la formule, pi 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.

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.

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

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

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 \frac{\log\log {n}}{{\log n}}\, .

Les 99 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

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

Inégalités

Certaines inégalités impliquant la fonction \varphi(n) 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,

et


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

Conjectures

Lien externe

Méthode de vérification empirique de la conjecture de Carmichael

Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Indicatrice d%27Euler ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fonction phi d'Euler de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Fonction d'Euler — 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 est utilisée pour les mathématiques pures, à la fois en théorie des groupes, en théorie algébrique… …   Wikipédia en Français

  • Fonction Polylogarithme — La fonction polylogarithme (aussi connue sous le nom de fonction de Jonquière) est une fonction remarquable et peut être définie pour tout s et |z|<1 par : Le paramètre s et l argument z sont pris sur l ensemble , l ensemble des nombres… …   Wikipédia en Français

  • Fonction Beta De Dirichlet — Fonction bêta de Dirichlet En mathématiques, la fonction β de Dirichlet, aussi appelée fonction ζ de Catalan, est un des exemples les plus simples de fonction L, après la fonction zêta de Riemann. C est un cas particulier de fonction L de… …   Wikipédia en Français

  • Fonction beta de Dirichlet — Fonction bêta de Dirichlet En mathématiques, la fonction β de Dirichlet, aussi appelée fonction ζ de Catalan, est un des exemples les plus simples de fonction L, après la fonction zêta de Riemann. C est un cas particulier de fonction L de… …   Wikipédia en Français

  • Fonction beta de dirichlet — Fonction bêta de Dirichlet En mathématiques, la fonction β de Dirichlet, aussi appelée fonction ζ de Catalan, est un des exemples les plus simples de fonction L, après la fonction zêta de Riemann. C est un cas particulier de fonction L de… …   Wikipédia en Français

  • Fonction zeta de Catalan — Fonction bêta de Dirichlet En mathématiques, la fonction β de Dirichlet, aussi appelée fonction ζ de Catalan, est un des exemples les plus simples de fonction L, après la fonction zêta de Riemann. C est un cas particulier de fonction L de… …   Wikipédia en Français

  • Fonction zêta de Catalan — Fonction bêta de Dirichlet En mathématiques, la fonction β de Dirichlet, aussi appelée fonction ζ de Catalan, est un des exemples les plus simples de fonction L, après la fonction zêta de Riemann. C est un cas particulier de fonction L de… …   Wikipédia en Français

  • Fonction β de Dirichlet — Fonction bêta de Dirichlet En mathématiques, la fonction β de Dirichlet, aussi appelée fonction ζ de Catalan, est un des exemples les plus simples de fonction L, après la fonction zêta de Riemann. C est un cas particulier de fonction L de… …   Wikipédia en Français

  • Fonction Diviseur — Cet article traite de la fonction diviseur. Pour la fonction sigma de Rado, voir Castor affairé (busy beaver). Sommaire 1 Definition 2 Propriétés 3 Fonction nombre de diviseurs …   Wikipédia en Français

  • Fonction sigma — Fonction diviseur Cet article traite de la fonction diviseur. Pour la fonction sigma de Rado, voir Castor affairé (busy beaver). Sommaire 1 Definition 2 Propriétés 3 Fonction nombre de diviseurs …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”