Indicatrice d'Euler

En mathématiques, l'indicatrice d'Euler est une fonction de la théorie des nombres.



Catégories :

Arithmétique modulaire

Page(s) en rapport avec ce sujet :

  • fonction indicatrice d'Euler) est équilante à la connaissance de la paire (p, q). En effet, si n est ... de 1 sont -1 et 1 modulo un nombre premier) ;... (source : bigbozoid.free)
  • premier avec n. On rappele que la fonction indicatrice d'Euler est la fonction qui associe à tout entier naturel non nul n, le nombre, noté ϕ (n), ... (source : www-fourier.ujf-grenoble)
  • Montrer que parmi quatre nombres réels deux à deux différents, .... montre qu'on trouve toujours deux réels αi et αj dans le premier tiroirs.... On rappelle que la fonction totient d'Euler (ou indicatrice d'Euler) est ... (source : irem.univ-lille1)
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 surtout en cryptologie.

La fonction indicatrice est aussi nommée fonction phi d'Euler ou simplement la fonction phi, car la lettre φ est couramment utilisée pour la désigner.

Elle est appelé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

A titre d'exemple, φ (8) = 4 car les quatre nombres 1, 3, 5 et 7 sont premiers avec 8. D'autre part φ (1) =1 - c'est l'unique nombre qui est égal à son indicatrice d'Euler.

Premières propriétés

Articles détaillés : Groupe cyclique et Anneau Z/nZ.

Dans ce paragraphe, n sert à désigner 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 sert à désigner un membre du groupe génèrant le groupe entier. Cette propriété est démontrée dans le paragraphe Théorème essentiel de l'article Groupe cyclique.

  • La valeur φ (n) est égale à l'ordre du groupe des unités de l'anneau Z/nZ.

Le groupe des unités sert à désigner la totalité 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 uniquement 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 par conséquent é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 essentiel 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, pi sert à désigner 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 ce dernier 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 sert à conclure la démonstration.

Autres propriétés

Arithmétique modulaire

L'indicatrice d'Euler est une fonction principale 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 beaucoup 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 spécifiquement des codes cycliques. Ce type de code se construit avec polynôme cyclotomique et le degré du polynôme cyclotomique Φn d'indice n à cœfficients dans les entiers est égal à φ (n). Plus exactement, 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 à l'ensemble des 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, μ sert à désigner la fonction de Möbius usuelle définie sur la totalité 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 zêta 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 qu'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 <img class=

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. Donc les valeurs de n correspondantes aux valeurs spécifiquement petites du rapport sont les n qui sont le produit d'un segment d'origine de la suite de l'ensemble des nombres premiers. À partir du théorème des nombres premiers il peut être montré qu'une constante ε dans la formule précédente peut donc ê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 <img class=
\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 :

<img class= 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 l'ensemble des n > 1 :

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

Pour un grand n aléatoire, ces limites ne peuvent pas être toujours perfectionné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 :

<img class=Conjectures

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Indicatrice_d%27Euler.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu