Somme avec indicatrice d'Euler

gnouk · June 2019

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.

gnouk · June 2019

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

LOU16 · June 2019

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

gnouk · June 2019

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 !

gnouk · June 2019

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"

reuns · June 2019

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

side · June 2019

supp

ev · June 2019

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

reuns · June 2019

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

side · June 2019

supp

reuns · June 2019

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

noix de totos · June 2019

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

Somme avec indicatrice d'Euler

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 17