Indicatrice d'Euler

emmanuel

Bonjour à tous,
Je m'excuse par avance de ne pas utiliser Latex, ce qui va rendre la lecture de mon énoncé peu confortable.
Je me casse les dents sur la démonstration d'un résultat qui, me semble-t-il, est archi connu: en notant Phi l'indicatrice d'Euler, n un entier naturel, d un diviseur de n,
montrer que la (somme (sur tous les diviseurs d de n) des Phi(d)) = n.

Ma tentative: une récurrence sur le nbe k de facteurs premiers de la décomposition de n. Je bloque sur le passage de k à k+1.

Merci à ceux qui savent...

Kashmir

Bonjour,

ce n'est pas une récurrence.
tu trouveras ce résultat dans le cours en téléchargement sur les anneaux et le corps de ce site, chapitre 5.

emmanuel

Merci de la référence qui amène aux polynômes cyclotomiques.
Néanmoins, il y a 1 point qui ne me saute pas aux yeux (comme il devrait, selon l'auteur):
en notant Rx (respectivement Fx) l'ensemble des racines x-ièmes (respectivement primitives x-ièmes) de l'unité, pourquoi a-t-on que {Fd, d divise n} réalise une partition de Rn?
Je ne dois pas être bien réveillé mais je n'arrive pas à démontrer ce résultat (qui est intuitivement évident).
Merci aux bonnes âmes...

Nono0

Parce que si a est une racine n-ième de l'unité c'est forcément une racine primitive d-ième (avec d=<n), et nécessairement d divise n.

Sinon, en posant la division euclidienne de n par d, on aurait n=a*d+b, avec b<d. Alors x^n=(x^(ad))*(x^b)=x^b=1, ce qui est contradictoire avec b<d et x racine primitive d-ième de l'unité.


AA

Kashmir

Si tu n'as pas la "vista" en passant par la cyclotomie, voici une autre possibilité de démonstration, qui elle n'exige aucune technique :

Soient les fractions $\frac{1}{n}$, $\frac{2}{n}$, ... , $\frac{n}{n}$.

Nous cherchons à les mettre sous forme irréductible $\frac{a}{d}$ où $d$ doit nécessairement diviser $n$.

Pour chaque $d$ divisant $n$, il y a $\phi(d)$ numérateurs $a$ possibles (puisque le nombre d'entiers $a$ tels que $a$ est premier avec $d$ est $\phi(d)$). Comme il y a en tout $n$ fractions, on en déduit le résultat.

borde1

Bonjour,

pour compléter la preuve de Kashmir, l'égalité demandée ici n'est autre, dans le formalisme du produit de convolution de Dirichlet des fonctions arithmétiques, que : $$\varphi \star 1 = \Id $$ où $\Id$ est la fonction identité et $1$ est la fonction arithmétique définie par $1(n)=1$ pour tout entier $n \geq 1$.

C'est bien sûr le cadre naturel de toutes ces égalités du type $\displaystyle{\sum_{d|n} f(d) g(\frac {n}{d})}$ que l'on peut trouver.

Signalons aussi que, par la formule d'inversion de Möbius, il vient : $$\varphi = \mu \star Id$$

Borde.

borde1

Il faut lire $\varphi \star 1 = Id$ à la ligne 4 et il manque un $Id$ à la ligne suivante (lire : "$Id$ est la fonction identité").

Borde.

emmanuel

Merci à vous 3:

Nono: je suis allé manger. Maintenant ca va mieux. C'est vrai que c'est évident.

Kashmir: du coup la démo via la cyclotomie me plaît bien (parce qu'elle ouvre la voie à d'autres résultats très intéressant dont une démo du Th de Wedderburn). Mais c'est vrai que la démo avec les n fractions i/n est sympa (à y regarder de près on retrouve la problématique de partition; ici c'est {a/d irreductible, a<=d, d divise n} qui réalise une partition de {i/n, i dans [1,n]}.

Borde: j'aime beaucoup les compléments et les perspectives nouvelles (ici le produit de convolution de Dirichlet des fonctions arithmétiques) que tu apportes. C'est très enrichissant.

Vianney

$$\varphi \star 1 = Id$$

borde1

Bonsoir,

Je remercie Emmanuel pour son jugement...

Pour compléter, rappelons- nous ce fait : on montre (voir n'importe quel bouquin de théorie multiplicative des nombres) que, si $f$ et $g$ sont 2 fonctions multiplicatives (ie $\gcd(m,n)=1 \Rightarrow f(mn)=f(m)f(n)$), alors $f \star g$ l'est aussi. Autrement dit, lorsqu'en pratique on doit montrer des formules similaires à celle proposée par notre ami Emmanuel, il est suffisant de la vérifier sur les puissances de nombres premiers $n=p^\alpha$. Le gain est énorme : les diviseurs de $p^\alpha$ sont très faciles à obtenir, et, souvent, la vérification de l'égalité se résume à un rapide calcul de routine...

Borde.