Show that $n | \sum_{k=1}^n m^{\textrm{gcd}(k, n)}$ where $n, m \geq 1$

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

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:

1. first, we show that for any $m, n \in M$ such that $(m; n)=1$ we also have $mn \in M$.
2. 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:

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

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