Somme avec indicatrice d'Euler
dans Arithmétique
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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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}.$$
$\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 !
Elle explique l'origine de cette formule, et pourquoi les calculs "marchent"
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)$
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.
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}})$
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}$.
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 https://www.math.stonybrook.edu/theses/thesis03-5/part1.pdf, 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 https://www.amazon.fr/Thèmes-darithmétique-Avec-exercices-corrigés/dp/2729827145/ref=sr_1_1?__mk_fr_FR=ÅMÅŽÕÑ&keywords=thèmes+d'arithmétique&qid=1561146275&s=gateway&sr=8-1, 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$.