Show that $n | \sum_{k=1}^n m^{\textrm{gcd}(k, n)}$ where $n, m \geq 1$ I must show that $n$ divides $\sum_{k=1}^n m^{\textrm{gcd}(k, n)}$ where $n, m \geq 1$.
When $n$ is prime, Fermat's theorem gives us the answer easily because then $\sum_{k=1}^n m^{\textrm{gcd}(k, n)} = m^n + (n-1)m \equiv 0  [n]$.
In the general case, how to show this? I would like to use mostly integers/arithmetics arguments, not too high level theories.
 A: Consider the set $$\mathcal{F} = \left( \mathbb{Z}/m\mathbb{Z}\right)^{\mathbb{Z}/n\mathbb{Z}}$$
of all functions $\varphi : \mathbb{Z}/n\mathbb{Z} \rightarrow \mathbb{Z}/m\mathbb{Z}$ (not group morphisms, just functions). Then you can define a group action of $\mathbb{Z}/n\mathbb{Z}$ over $\mathcal{F}$ by
$$\begin{array}{}
 & \mathbb{Z}/n\mathbb{Z} \times\mathcal{F} & \longrightarrow & \mathcal{F} \\
    & \quad \quad( k,\varphi)  & \longmapsto & (x \mapsto \varphi(x+k)) \end{array}$$
Let's count the number of fixed points of an element $k \in \mathbb{Z}/n\mathbb{Z} $ for this action. A function $\varphi$ is fixed by $k$ if $\varphi$ is constant on the orbits of the natural (additive) action of $k$ on $\mathbb{Z}/n\mathbb{Z}$ : by a classical fact, this action has exactly $\gcd(k,n)$ orbits, so you have exactly $m^{\gcd(k,n)}$ functions from $\mathbb{Z}/n\mathbb{Z}$ to $\mathbb{Z}/m\mathbb{Z}$ that are constant on these orbits, i.e. $k$ has exactly $m^{\gcd(k,n)}$ fixed points for the action of $\mathbb{Z}/n\mathbb{Z}$ on $\mathcal{F}$.
You can then apply Burnside's formula to get that
$$\mathrm{Card}(\mathcal{F}/(\mathbb{Z}/n\mathbb{Z})) = \frac{1}{n} \sum_{k=1}^n m^{\gcd(k,n)}$$
so, since the LHS is an integer, $n$ must divide $\sum_{k=1}^n m^{\gcd(k,n)}$.
A: In order to give a fully arithmetic answer to the problem, let us introduce a couple of notations:

*

*we denote by $\mathbb{P}$ the set of all strictly positive prime integers, in other words the set of what is commonly understood as prime numbers (from the strict algebraic point of view, $0$ and $-2$ are both prime elements of the ring $\mathbb{Z}$).

*for given $r \in \mathbb{Z}$ we denote by $\mathrm{D}(r)\colon=\{k \in \mathbb{N}|\ k \mid r\}$ the set of all its natural divisors.

*for given $r \in \mathbb{Z}$ we introduce the set $\Pi(r)\colon=\{p \in \mathbb{P}|\ p\mid r\}$ of all its prime divisors.

*for given $n \in \mathbb{N}$ we define the set $\mathrm{P}(n)\colon=\{k \in \mathbb{N}|\ 1 \leqslant k \leqslant n \wedge (k; n)=1\}$ of all nonzero natural numbers less than $n$ and coprime with it. We have also tacitly used the notation $(r; s)$ to indicate the greatest common divisor of given integers $r, s \in \mathbb{Z}$ (the role of the semicolon in the notation being to prevent confusion with the syntax for ordered pairs). When $n \in \mathbb{N}^{\times}\colon=\mathbb{N} \setminus \{0\}$, we have by definition that $|\mathrm{P}(n)|=\varphi(n)$.

*for any two integers $r, s \in \mathbb{Z}$, we denote by $[r, s]$ the integer and not the real interval between $r$ and $s$.

*for any $n \in \mathbb{N}^{\times}$ we introduce the polynomial $P_n\colon=\displaystyle\sum_{k=1}^n X^{(k; n)} \in \mathbb{Z}[X]$.

With the above notation, our goal is to show that for any $n \in \mathbb{N}^{\times}$ and any $m \in \mathbb{Z}$ the relation $n \mid P_n(m)$ holds, or more succinctly put that the subset:
$$M\colon=\left\{n \in \mathbb{N}^{\times}|\ \{P_n(m)\}_{m \in \mathbb{Z}} \subseteq n\mathbb{Z}\right\}$$
is equal to its entire ambient set $\mathbb{N}^{\times}$.
Before moving on to the core of the proof, a preliminary result is needed:

Proposition. For every $n \in \mathbb{N}^{\times}$ we have the expression $P_n=\displaystyle\sum_{d \in \mathrm{D}(n)}\varphi\left(\frac{n}{d}\right)X^d=\displaystyle\sum_{d \in \mathrm{D}(n)}\varphi(d)X^{\frac{n}{d}}$.

Proof. The second equality is a simple consequence of the fact that the map:
$$\begin{align*}
\mathrm{D}(n) &\to \mathrm{D}(n)\\
d &\mapsto \frac{n}{d}
\end{align*}$$
is an involutive permutation of the set $\mathrm{D}(n)$ of summation indices. To establish the first one, let us start by remarking that the map:
$$\begin{align*}
\delta \colon [1, n] &\to \mathrm{D}(n)\\
\delta(k)&=(k; n)
\end{align*}$$
is clearly a surjection whose fibre at every element in the codomain is given by $\delta^{-1}[\{d\}]=d\mathrm{P}\left(\frac{n}{d}\right)$. This means that $\left(d\mathrm{P}\left(\frac{n}{d}\right)\right)_{d \in \mathrm{D}(n)}$ is a partition of $[1, n]$ and we thus have:
$$P_n=\sum_{d \in \mathrm{D}(n)}\sum_{k \in d\mathrm{P}\left(\frac{n}{d}\right)}X^{\delta(k)}=\sum_{d \in \mathrm{D}(n)}\sum_{k \in d\mathrm{P}\left(\frac{n}{d}\right)}X^d=\sum_{d \in \mathrm{D}(n)}\left|d\mathrm{P}\left(\frac{n}{d}\right)\right|X^d=\sum_{d \in \mathrm{D}(n)}\varphi\left(\frac{n}{d}\right)X^d,$$
concluding our proof. $\Box$
We organise the proof in the following two steps:

*

*first, we show that for any $m, n \in M$ such that $(m; n)=1$ we also have $mn \in M$.

*second, we show that for any prime $p \in \mathbb{P}$ and for any exponent $k \in \mathbb{N}$ we have $p^k \in M$.

Establishing the two assertions above is sufficient, for it allows us to prove that $\mathbb{N}^{\times} \subseteq M$ by induction on $|\Pi(n)|$ for arbitrary nonzero natural $n$ (argument which of course relies on the Fundamental Theorem of Arithmetic; note that the base case of this induction corresponds to the claim $1 \in M$, which is clearly true). Let us now justify each of the two claims above:

*

*Here we begin by establishing another auxiliary result:


Proposition. Let $m, n \in \mathbb{N}^{\times}$ be coprime, $(m; n)=1$. Then the map:
$$\begin{align*}
\mathrm{D}(m) \times \mathrm{D}(n) &\to \mathrm{D}(mn)\\
(k, l) &\mapsto kl
\end{align*}$$
is a bijection.

Proof. Consider first two pairs of divisors $(k, l), (k', l') \in \mathrm{D}(m) \times \mathrm{D}(n)$ such that $kl=k'l'$. Since $l, l' \mid n$ it is obvious that $(m; l), (m; l') \mid (m; n)=1$ and therefore $(m; l)=(m; l')=1$. Thus, from one of the fundamental properties of the g.c.d operation it follows that $(m; kl)=(m; k)=k$ and analogously $(m; k'l')=(m; k')=k'$. Since $kl=k'l'$ we immediately deduce that $k=k'$ and subsequently $l=l'$ (for $0 \notin \mathrm{D}(n)$ as long as $n\neq0$). This shows that the map introduced above is injective. As to its surjectivity, consider an arbitrary $h \in \mathrm{D}(mn)$ and define $k\colon=(m; h) \in \mathrm{D}(m)$. If we further introduce $l\colon=\frac{h}{k}$ we gather that $\left(\frac{m}{k}, l\right)=1$, by virtue of another fundamental property of the g.c.d operation. From $h \mid mn$ we infer that $l \mid \frac{m}{k}n$ and taking into account that $l$ and $\frac{m}{k}$ are relatively prime we gather that $l \mid n$. Thus, $l \in \mathrm{D}(n)$ and we have expressed $h=kl$ as a product of the divisors $k \in \mathrm{D}(m)$ and $l \in \mathrm{D}(n)$, which means that our map is also surjective. $\Box$
We continue by putting to use the result above in order to remark that given coprime nonzero natural numbers $m$ and $n$ we have:
$$\begin{align*}
P_{mn}&=\sum_{h \in \mathrm{D}(mn)}\varphi\left(\frac{mn}{h}\right)X^h\\
&=\sum_{\substack{k \in \mathrm{D}(m) \\ l \in \mathrm{D}(n)}}\varphi\left(\frac{mn}{kl}\right)X^{kl}\\
&=\sum_{\substack{k \in \mathrm{D}(m) \\ l \in \mathrm{D}(n)}}\varphi\left(\frac{m}{k}\frac{n}{l}\right)X^{kl}\\
&=\sum_{k \in \mathrm{D}(m)}\sum_{l \in \mathrm{D}(n)}\varphi\left(\frac{m}{k}\right)\varphi\left(\frac{n}{l}\right)X^{kl}\\
&=\sum_{k \in \mathrm{D}(m)}\varphi\left(\frac{m}{k}\right)\sum_{l \in \mathrm{D}(n)}\varphi\left(\frac{n}{l}\right)\left(X^k\right)^l\\
&=\sum_{k \in \mathrm{D}(m)}\varphi\left(\frac{m}{k}\right)P_n\left(X^k\right)
\end{align*}$$
together with the analogous relation (obtained by considering $\mathrm{D}(n)$ as the outer domain of summation):
$$P_{mn}=\sum_{l \in \mathrm{D}(n)}\varphi\left(\frac{n}{l}\right)P_m\left(X^l\right).$$
The coprimeness of $m$ and $n$ is essential in order to justify the relation $\varphi\left(\frac{m}{k}\frac{n}{l}\right)=\varphi\left(\frac{m}{k}\right)\varphi\left(\frac{n}{l}\right)$, bearing in mind that $\left(\frac{m}{k}; \frac{n}{l}\right) \mid (m; n)=1$.
Let us now consider arbitrary $r \in \mathbb{Z}$. If $m, n \in M$ we have $m \mid P_m(s)$ and similarly $n \mid P_n(s)$ for any $s \in \mathbb{Z}$. From the above relations we obtain in particular that:
$$\begin{align*}
P_{mn}(r)&=\sum_{l \in \mathrm{D}(n)}\varphi\left(\frac{n}{l}\right)P_m\left(r^l \right) \in m\mathbb{Z}\\
P_{mn}(r)&=\sum_{k \in \mathrm{D}(m)}\varphi\left(\frac{m}{k}\right)P_n\left(r^k \right) \in n\mathbb{Z},
\end{align*}$$
hence $P_{mn}(r) \in m\mathbb{Z} \cap n\mathbb{Z}=mn\mathbb{Z}$, the latter relation between ideals of $\mathbb{Z}$ also being valid by virtue of $(m; n)=1$. This means that $mn \in M$ and establishes our first claim.


*Here again we proceed by induction on the exponent $k$ in order to show that $p^k \in M$ for all $k \in \mathbb{N}$, the base case $k=0$ being equivalent to $1 \in M$ and thus trivial by definition of $M$. To this end, we first remark the general relation:
$$P_{p^k}=\sum_{i=0}^k \varphi\left(p^i\right)X^{p^{k-i}}=X^{p^k}+\sum_{i=1}^k p^{i-1}(p-1)X^{p^{k-i}},$$
based on the fact that the map:
$$\begin{align*}
[0, k] &\to \mathrm{D}\left(p^k\right)\\
i &\mapsto p^i
\end{align*}$$
is a bijection and we employ this general relation to derive the recursive relation:
$$\begin{align*}
P_{p^{k+1}}&=X^{p^{k+1}}+\sum_{i=1}^{k+1}p^{i-1}(p-1)X^{p^{k+1-i}}\\
&=X^{p^{k+1}}+\sum_{i=0}^k p^i(p-1)X^{p^{k-i}}\\
&=X^{p^{k+1}}+(p-1)X^{p^k}+\sum_{i=1}^k p^i(p-1)X^{p^{k-i}}\\
&=X^{p^{k+1}}+(p-1)X^{p^k}+p\sum_{i=1}^k p^{i-1}(p-1)X^{p^{k-i}}\\
&=X^{p^{k+1}}-X^{p^k}+p\left(X^{p^k}+\sum_{i=1}^k p^{i-1}(p-1)X^{p^{k-i}}\right)\\
&=X^{p^{k+1}}-X^{p^k}+pP_{p^k}.
\end{align*}$$
Consider now an arbitrary $m \in \mathbb{Z}$. Since by the inductive assumption we are given that $p^k \in M$, we infer $P_{p^k}(m) \in p^k\mathbb{Z}$ and subsequently $pP_{p^k}(m) \in p^{k+1}\mathbb{Z}$. Thus, in order to show that $P_{p^{k+1}}(m) \in p^{k+1}\mathbb{Z}$ for arbitrary $m \in \mathbb{Z}$ and hence conclude that $p^{k+1} \in M$, it suffices to establish the following “higher order” version of Fermat’s little theorem:
$$(\forall k, m)\left(k \in \mathbb{N} \wedge m \in \mathbb{Z} \Rightarrow m^{p^{k+1}} \equiv\ m^{p^k} \left(\mathrm{mod}\ p^{k+1}\right)\right),$$
for fixed prime $p \in \mathbb{P}$.

Let us first remark that for fixed $k \in \mathbb{N}$ and any multiple $m \in p\mathbb{Z}$ of $p$ we have the obvious relation $p^{p^{k}} \mid m^{p^k}\left(m^{p^k(p-1)}-1\right)=m^{p^{k+1}}-m^{p^k}$ and since $p \geqslant 2$ we can also infer that $p^k \geqslant 2^k \geqslant k+1$ (it is a fundamental Bernoulli-type inequality that $2^n \geqslant n+1$ for any $n \in \mathbb{N}$). It then follows that in the particular case $p \mid m$ we therefore have $p^{k+1} \mid p^{p^k} \mid m^{p^{k+1}}-m^{p^k}$, which establishes the higher order claim.
In order to prove this higher order version for non-multiples of $p$ we once again resort to induction on $k$. The base case $k=0$ is none other than Fermat’s little theorem. Assuming the claim to be valid for arbitrary $k \in \mathbb{N}$ we establish it for $k+1$. Let $m \in \mathbb{Z} \setminus p\mathbb{Z}$. We have the factorisation:
$$\begin{align*}
m^{p^{k+2}}-m^{p^{k+1}}&=m^{p^{k+1}}\left(m^{p^{k+1}(p-1)}-1\right)\\
&=m^{p^{k+1}}\left(\left(m^{p^k(p-1)}\right)^p-1\right)\\
&=m^{p^{k+1}}\left(m^{p^k(p-1)}-1\right)\sum_{l=0}^{p-1}\left(m^{p^k(p-1)}\right)^l\\
&=m^{p^k(p-1)}\left(m^{p^{k+1}}-m^{p^k}\right)\sum_{l=0}^{p-1}\left(m^{p^k(p-1)}\right)^l,
\end{align*}$$
from which we gather that, in conjunction with the induction hypothesis according to which $m^{p^{k+1}}-m^{p^k} \in p^{k+1}\mathbb{Z}$, in order to show that $m^{p^{k+2}}-m^{p^{k+1}} \in p^{k+2}\mathbb{Z}$ it suffices to show that $p \mid \displaystyle\sum_{l=0}^{p-1}\left(m^{p^k(p-1)}\right)^l=\sum_{l=0}^{p-1}\left(m^{p^kl}\right)^{p-1}$. However, since by hypothesis $p \nmid m$ we also have that $p \nmid m^{p^kl}$ for any $l \in [0, p-1]$, whence by virtue of Fermat’s little theorem we infer that $\left(m^{p^kl}\right)^{p-1} \equiv\ 1 \left(\mathrm{mod}\ p\right)$ and finally that:
$$\sum_{l=0}^{p-1}\left(m^{p^kl}\right)^{p-1} \equiv\ \sum_{l=0}^{p-1}1=p \equiv\ 0 \left(\mathrm{mod}\ p\right),$$
which fully establishes our claim and brings our argument to an end.
A: Not an answer. Too long for a comment. The below might be helpful.
$$\sum_{k=1}^n m^{\gcd(k,n)} = \sum_{d \mid n} \sum_{\substack{1 \le k \le n \\ \gcd(k,n) = d}} m^d = \sum_{d \mid n} m^d \sum_{\substack{1 \le k \le n \\ d \mid k \\ \gcd(\frac{k}{d},\frac{n}{d}) = 1}} 1 = \sum_{d \mid n} m^d \sum_{\substack{1 \le r \le n/d \\ \gcd(r,\frac{n}{d}) = 1}} 1$$ $$ = \sum_{d \mid n} m^d \sum_{1 \le r \le n/d} \sum_{s \mid \gcd(r,\frac{n}{d})} \mu(s) = \sum_{d \mid n} m^d \sum_{1 \le r \le n/d} \sum_{\substack{s \mid r \\ s \mid n/d}} \mu(s) = \sum_{d \mid n} m^d \sum_{s \mid n/d} \mu(s) \sum_{\substack{1 \le r \le n/d \\ s \mid r}} 1$$ $$ = \sum_{d \mid n} m^d \sum_{s \mid n/d} \mu(s)\frac{n}{ds} = \left(\sum_{ds \mid n} \frac{m^d}{d}\frac{\mu(s)}{s}\right)n.$$
