, 2025

Proof 1: By induction, $z_n$ can be uniquely determined from the equation
$$nz_n = \left( \sum_{k|n} k x_k^{n/k} \right) \cdot \left( \sum_{k|n} k y_k^{n/k} \right) - \sum_{\substack{k|n \\ k<n}} k z_k^{n/k}. \qquad (3)$$
We only need to prove that the right-hand side is divisible by $n$. To this end, it suffices to show that for any prime factor $p$ of $n$, if $p^r \nmid n$ ($r \in \mathbb{N}_+$), then $p^r$ divides the right-hand side of (3).
Working modulo $p^r$, we first remove terms in (3) whose coefficients are already multiples of $p^r$:
$$\begin{aligned} nz_n &\equiv \left( \sum_{\substack{k|n \\ p^r \nmid k}} k x_k^{n/k} \right) \cdot \left( \sum_{\substack{k|n \\ p^r \nmid k}} k y_k^{n/k} \right) - \sum_{\substack{k|n \\ p^r \nmid k}} k z_k^{n/k} \\ &= \left( \sum_{k|\frac{n}{p}} k x_k^{n/k} \right) \cdot \left( \sum_{k|\frac{n}{p}} k y_k^{n/k} \right) - \sum_{k|\frac{n}{p}} k z_k^{n/k} \quad (\text{mod } p^r). \end{aligned} \qquad (4)$$
We first prove a simple lemma: For any integer $a$ and positive integer $t$, $a^{pt} \equiv a^{pt-1} \pmod{p^t}$.
Indeed, if $p \nmid a$, then since $p^{t-1} \ge t$, both $a^{pt}$ and $a^{pt-1}$ are divisible by $p^t$. If $p \nmid a$, then $a^{p-1} - 1$ is divisible by $p$, and by the lifting-the-exponent lemma, $a^{(p-1)p^{t-1}} \equiv 1 \pmod{p^t}$, so $a^{pt} \equiv a^{pt-1} \pmod{p^t}$.
Returning to the problem, we now show that for any $k \mid \frac{n}{p}$ and any integer $a$, $ka^{n/k} \equiv ka^{n/pk} \pmod{p^r}$. Indeed, let $s = v_p(k) < r$. It suffices to prove $a^{n/k} \equiv a^{n/pk} \pmod{p^{r-s}}$. By the lemma, $a^{p^{r-s}} \equiv a^{p^{r-s-1}} \pmod{p^{r-s}}$. Raising this congruence to the $n/p^{r-s}$-th power yields the result.
Thus, $nz_n$ satisfies
$$nz_n \equiv \left( \sum_{k|\frac{n}{p}} k x_k^{n/pk} \right) \cdot \left( \sum_{k|\frac{n}{p}} k y_k^{n/pk} \right) - \sum_{k|\frac{n}{p}} k z_k^{n/pk} = 0 \pmod{p^r}.$$
---

Proof 2: For any positive integer $L$, define the polynomial
$$g_L(t) = \sum_{d|L} t^d \mu\left(\frac{L}{d}\right),$$
where $\mu(\cdot)$ is the Möbius function. We now show that for any integer $t$, $g_L(t)$ is always divisible by $L$. Without loss of generality, assume $t$ is a positive integer. Note that the number of distinct circular arrangements of length $L$ with exactly $L$ as the minimal period (rotations considered identical) using $t$ colors is precisely $\frac{1}{L}g_L(t)$. Thus, $g_L(t)$ is divisible by $L$.
For any positive integer $m$, define
$$A_m = \sum_{L|m} L g_{\frac{m}{L}}(x_L), \quad B_m = \sum_{L|m} L g_{\frac{m}{L}}(y_L).$$
By the above discussion, $A_m$ is divisible by $m$. By Möbius inversion,
$$\begin{align*} \sum_{m|n} A_m &= \sum_{L|m|n} L g_{\frac{m}{L}}(x_L) = \sum_{L|m|n} L \sum_{d|\frac{m}{L}} x_L^d \mu\left(\frac{m}{dL}\right) = \sum_{dL|n} L x_L^d \cdot \sum_{\substack{\frac{m}{dL} \\ \frac{n}{dL}}} \mu\left(\frac{m}{dL}\right) \\ &= \sum_{dL|n} L x_L^d \cdot \mathbf{1}_{\frac{n}{dL}=1} = \sum_{dL=n} L x_L^d = \sum_{k|n} k x_k^{n/k}. \end{align*}$$
We need to find a sequence of positive integers $\{C_n\}$ such that for all positive integers $n$,
$$\sum_{m|n} C_m = \left( \sum_{m|n} A_m \right) \left( \sum_{m|n} B_m \right).$$
In fact, we can take $C_n = \sum_{=n} A_u B_v$, i.e., the sum over all pairs $(u,v)$ with least common multiple $= n$. Since $A_u B_v$ is divisible by both $uv$ and $n$, it follows that $C_n$ is divisible by $n$.
Finally, for $n = 1, 2, 3, \dots$, we sequentially define
$$z_n = \frac{1}{n} \left[ C_n - \sum_{L|n, L<n} L g_{\frac{n}{L}}(z_L) \right]$$
to satisfy the requirement.