Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
256 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Somme avec indicatrice d'Euler

Envoyé par gnouk 
Somme avec indicatrice d'Euler
il y a cinq mois
Bonjour
Il s'agit de montrer que pour tout entier relatif $k$ et tout entier naturel non nul $n$ la quantité $\displaystyle \sum_{d\mid n} k^d \varphi \Big( \frac{n}{d} \Big)$ est un multiple de $n$.

Je me suis placé dans $\mathbb{Z}/n\mathbb{Z}$, j'ai essayé d'introduire la fonction $\mu$ de Möbius, de raisonner par récurrence sur $k$, mais je bloque. Quelqu'un a-t-il déjà vu cet exercice ?
Merci d'avance.



Edité 2 fois. La dernière correction date de il y a cinq mois et a été effectuée par AD.
Re: Somme avec indicatrice d'Euler
il y a cinq mois
J'ai essayé avec $n=p$ un nombre premier, puis $n=p^2$, c'est ok . Je pense y arriver avec $n=p^j$ peut-être par récurrence sur $j$. Puis après décomposer $n$ en facteurs premiers ? Cela me semble compliqué.
Re: Somme avec indicatrice d'Euler
il y a cinq mois
Bonsoir,
Ce problème peut en effet se révéler difficile pour celui à qui il n'a jamais été indiqué l'emplacement de "la" solution.

Soient $k,n \in \N^*,\ \mathcal F$ l'ensemble des applications de $ E=\Z/n\Z$ dans $[\![1;k]\!]$.
Alors le groupe $G=\Z/n\Z\:$ opère sur $\mathcal F$ par : $\:\forall (g,f ,x) \in G\times \mathcal F\times E,\quad f^g (x) = f(g+x)$.
Et il se trouve qu'il existe une formule de dénombrement attribuée à Burnside, qui, appliquée à ce contexte ("problème des colliers"), donne:
$$\displaystyle \dfrac 1n \sum _{d\mid n} k^d \varphi \left(\dfrac nd \right)\:\text{ est le nombre d'orbites de}\: \mathcal F\: \text {sous l'action de G}.$$
D'autre part,$\:\forall k \in \Z,\ \exists k_1 \in \N^*\ \text{tel que}\ k \equiv k_1 \mod n \:$. Ainsi, $$
\boxed { \displaystyle \forall (k,n) \in \Z\times \N^*, \ \sum _ {d\mid n }^{\phantom n} k^d \varphi \Big( \dfrac nd\Big) \equiv 0 \mod n}.$$



Edité 8 fois. La dernière correction date de il y a cinq mois et a été effectuée par LOU16.
Re: Somme avec indicatrice d'Euler
il y a cinq mois
Finalement, en posant $n=p^a q$ avec $p \wedge q=1$, on arrive, en écrivant $d=p^bd^\prime$, avec $d^\prime | q$, et en utilisant
$\varphi(n/d)=\varphi(p^{a-b})\varphi(q/d^\prime)$ à montrer que la somme est divisible par $p^a$, et c'est fini.

Au passage il fallait démontrer ce lemme $k^{p^{a+1}}-k^{p^a}$ est divisible par $p^{a+1}$ lorsque $p$ est premier !

Mais si quelqu'un a une solution plus directe, je suis preneur !



Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par AD.
Re: Somme avec indicatrice d'Euler
il y a cinq mois
Merci Lou16 pour cette indication. J'ai entendu parler de cette formule dans le cas général.. je vais regarder de plus près comment elle s'applique ici…

Elle explique l'origine de cette formule, et pourquoi les calculs "marchent"
Re: Somme avec indicatrice d'Euler
il y a cinq mois
Il n'y a pas vraiment de preuve plus simple. Juste c'est le nombre de colliers (necklaces) :

Soit $f \in \{1\ldots k\}^n$ et $T f_j = f_{j+1}$ où les indices sont pris modulo $n$

alors $\sum_{m | d} \mu(m) k^{d/m} = \#\{ f \in \{1\ldots k\}^n, T^d f = f, \forall m < d, T^m f \ne f\}$ est le nombre de suites de période exactement $d$
et $\frac{1}{d} \sum_{m | d} \mu(m) k^{d/m} = \#\{ \{\bigcup T^j f\}, f \in \{1\ldots k\}^n, T^d f = f, \forall m < d, T^m f \ne f\}$ est le nombre de colliers de période exactement $d$

et $\sum_{d | n} \frac{1}{d} \sum_{m | d} \mu(m) k^{d/m} = \#\{ \{\bigcup T^j f\}, f \in \{1\ldots k\}^n\}$ est le nombre total de colliers

finalement $\sum_{d | n} \frac{1}{d} \sum_{m | d} \mu(m) k^{d/m} =\frac1n \sum_{d | n} k^d \varphi(n/d)$



Edité 4 fois. La derni&egrave;re correction date de il y a cinq mois et a &eacute;t&eacute; effectu&eacute;e par reuns.
Re: Somme avec indicatrice d'Euler
il y a cinq mois
bonsoir,

curiosité et démonstration en 1 ligne (mais assez inexplicable) dans le cas où $k=p^r$ où $p$ est un nombre premier comme conséquence d'un résultat d'arithmétique de $F_q[X], q=p^r$.
La formule à démontrer m'en rappelait une autre qui dénombre le nombre $I_q(n)$ de polynômes irréductibles de $F_q[X]$, unitaires de degré $n$.
Je suis allé voir dans le livre "théorie de Galois" d'Escofier qui démontre en exercice la formule suivante $nI_q(n)=\sum _{d\mid n} \mu(n/d)q^d$.

A partir de ça, j'ai pu en dériver par une démonstration très courte (en bas du fil) le résultat dans le cas où $k$ est une puissance d'un nombre premier.

Notations :
$p$ premier, $r$ entier non nul, $k=p^r$
Soit $f$ la fonction définie sur $N^*$ par $\forall n\in N^*, f(n)=k^n$
Soit $g$ la fonction identité sur $N^*$
Soit $1$ la fonction constante égale à 1 sur $N^*$
Soit $\delta$ la fonction définie sur $N^*$, $\delta(1)=1, \forall n>1, \delta(n)=0$ qui est élément neutre de l'algèbre de Dirichlet.

Le résultat d'arithmétique de $F_k[X]$ s'écrit $\forall n\in N^*, nI_k(n)=\sum _{d\mid n}\mu(n/d)k^d=f* \mu(n)$

Rappels :
Le produit de convolution $*$ (je ne rappelle pas sa définition) est associatif et commutatif
$\phi*1=g$ (c'est juste la réécriture de la formule $\forall n\in N^*, n=\sum _{d\mid n} \phi(d)$)
$1*\mu=\delta$, (formule d'inversion de Möbius ou plus exactement une formulation équivalente)

Démonstration :
On a $f*\phi=(f*\phi)*(1*\mu)=(f*\mu)*g$ et donc $\forall n\in N^*, f*\phi(n)=\sum _{d\mid n}dI_k(d) n/d=n\sum _{d\mid n}I_k(d)$, ce qui démontre le résultat.

Je ne sais pas si on peut étendre cette démonstration à $k$ non puissance d'un nombre premier. Par ailleurs, je ne comprends absolument pas le rapport avec l'arithmétique de $F_q [X]$

Quelqu'un a-t-il une explication ?


Post publication :
pour info. en 1ère page du forum arithmétique, il y a la question de Raboteux intitulée "fonction de Möbius". Au cours de ce fil, il donne une preuve du calcul du nombre de polynômes unitaires irréductibles de $F_q[X]$.



Edité 2 fois. La derni&egrave;re correction date de il y a cinq mois et a &eacute;t&eacute; effectu&eacute;e par side.
ev
Re: Somme avec indicatrice d'Euler
il y a cinq mois
avatar
@ Side

La fonction arithmétique \( f(n) = \displaystyle \sum_{d\mid n} k^d \varphi \Big( \frac{n}{d} \Big) \) est multiplicative comme convolée d'une fonction (complètement) multiplicative par une fonction multiplicative. Elle est donc multiplicative.

Tu obtiens alors tout ce que tu veux.

Non ?

e.v.
Re: Somme avec indicatrice d'Euler
il y a cinq mois
$d \mapsto \frac{\log(k^d)}{\log k}$ est multiplicative mais pas $d \mapsto k^d$

Ce que je me demande c'est si on peut utiliser que le résultat est vrai pour $k = p^r$ pour dire qu'il est vrai pour tout $k$ (si un polynôme rationnel prend des valeurs entières sur les $p^r$ alors ...)

Enfin on peut interpréter les polynômes irréductibles de $\Bbb{F}_{p^r}[x]$ comme des colliers : soit $a$ une racine alors $\prod_{j=1}^d (x-a^{q^j})$ correspond au collier $(a,a^q,a^{q^2}, \ldots,a^{q^{d-1}})$



Edité 2 fois. La derni&egrave;re correction date de il y a cinq mois et a &eacute;t&eacute; effectu&eacute;e par reuns.
Re: Somme avec indicatrice d'Euler
il y a cinq mois
Bonsoir,


1) Après de veines tentatives, je n'ai pas réussi à montrer que :

'' Si un polynôme à coefficients rationnels prend en toute puissance d'un nombre premier $p$ une valeur entière alors il prend une valeur entière sur tout entier relatif.''

Je ne sais pas si ce résultat est vrai ou pas.

Il suffirait pour démontrer l'implication : si la relation est vraie pour tout $k$ puissance d'un nombre premier alors elle est vraie pour tout entier relatif.


2) le théorème de la progression arithmétique de Dirichlet permet de prouver que le résultat est vrai pour tout entier $k$ premier avec $n$ (on tire profit du fait que la relation est vraie pour $k=1$).

Là aussi je n'ai pas réussi à etendre le résultat pour tout $k$.
Re: Somme avec indicatrice d'Euler
il y a cinq mois
Soit $A \subset \Bbb{Z}$ et $f(x)= \frac{1}{m} F(x), F \in \Bbb{Z}[x] $ un polynôme rationnel de degré $d$ qui prend des valeurs entières sur $A$.

Soit $u(a) = (1,a,a^2,\ldots,a^d) \in \Bbb{Z}^{d+1}$.

Ce dont on a besoin c'est que pour tout $n$ :

$\qquad$ pour tout $p^k$, $\ \ $ $u(n) \bmod p^k$ s'exprime comme une combinaison $\Bbb{Z}$-linéaire de $u(a),a\in A$.

Si c'est le cas avec $p^k$ la plus grande puissance de $p$ qui divise $m$ alors $u(n) \equiv \sum_j c_j u(a_j) \bmod p^k$ donc $F(a_j) \equiv 0 \bmod p^k \implies F(n) \equiv \sum_j c_j F(a_j) \equiv 0 \bmod p^k$ et donc le dénominateur de $f(n) = \frac{F(n)}{m}$ ne contient pas de puissances de $p$.

Comme c'est vrai pour tout $p$ alors $f(n) \in \Bbb{Z}$ et donc $f$ prends des valeurs entières sur $\Bbb{Z}$.



Edité 3 fois. La derni&egrave;re correction date de il y a cinq mois et a &eacute;t&eacute; effectu&eacute;e par reuns.
Re: Somme avec indicatrice d'Euler
il y a cinq mois
On peut aussi utiliser le concept de suites réalisables.

On rappelle que :

(i) Si $k \in \mathbb{Z}_{\geqslant 1}$ est fixé, la suite $(k^n)_n$ est réalisable. Pour une démonstration, voir [www.math.stonybrook.edu], Proposition 1.2.3 page 8.

(ii) Si $u = (u_n)$ est une suite réalisable d'entiers positifs ou nuls, alors $(u \star \mu)(n) \equiv 0 \pmod n$, où $(f \star g)(n) = \sum_{d \mid n} f(d) g(n/d)$ désigne l'habituel produit de convolution de Dirichlet des fonctions arithmétiques $f$ et $g$. Pour une démonstration, voir [www.amazon.fr], Exercice 4.11 page 127.

Des points (i) et (ii), il vient pour tous $n,k \in \mathbb{Z}_{\geqslant 1}$
$$\sum_{d \mid n} k^d \mu(n/d) \equiv 0 \pmod n.$$
On conclut alors en utilisant la convolution $\varphi = \mu \star \textrm{id}$ (facile à vérifier, quant à elle, car les fonctions en jeu sont multiplicatives), ce qui donne, pour tous $n,k \in \mathbb{Z}_{\geqslant 1}$
$$\sum_{d \mid n} k^d \varphi(n/d) = \sum_{d \mid n} k^d \left( \sum_{e \mid (n/d)} \mu(e) \frac{n}{de} \right) $$
et en posant $h=de$, il vient
$$\sum_{d \mid n} k^d \varphi(n/d) = \sum_{h \mid n} \sum_{d \mid h} k^d \mu \left( \frac{h}{d} \right) \frac{n}{h} = n \sum_{h \mid n} \frac{1}{h} \left( \sum_{d \mid h} k^d \mu \left( \frac{h}{d} \right) \right) \equiv 0 \pmod n $$
puisque la somme intérieure est $\equiv 0 \pmod h$ pour tout diviseur $h$ de $n$.



Edité 2 fois. La derni&egrave;re correction date de il y a cinq mois et a &eacute;t&eacute; effectu&eacute;e par noix de totos.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 138 297, Messages: 1 342 472, Utilisateurs: 24 787.
Notre dernier utilisateur inscrit CGO.


Ce forum
Discussions: 5 132, Messages: 62 216.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page