2025 International Mathematical Olympiad China National Team Selection Test

Proof 1: By induction, $z_n$ can be uniquely determined from the equation $$n{z}_n=\left(\sum _{k|n}k{x}_k^{n/k}\right)\cdot \left(\sum _{k|n}k{y}_k^{n/k}\right)-\sum _{\begin{array}{c}k|n\\ k<n\end{array}}k{z}_k^{n/k}.(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{array}{rl}n{z}_n& \equiv \left(\sum _{\begin{array}{c}k|n\\ p^r\nmid k\end{array}}k{x}_k^{n/k}\right)\cdot \left(\sum _{\begin{array}{c}k|n\\ p^r\nmid k\end{array}}k{y}_k^{n/k}\right)-\sum _{\begin{array}{c}k|n\\ p^r\nmid k\end{array}}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}(\text{mod }{p}^r).\end{array}(4)$$ We first prove a simple lemma: For any integer $a$ and positive integer $t$, $a^{pt}\equiv a^{pt-1}(\mathrm{mod}{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(\mathrm{mod}{p}^t)$, so $a^{pt}\equiv a^{pt-1}(\mathrm{mod}{p}^t)$. Returning to the problem, we now show that for any $k\mid \frac{n}{p}$ and any integer $a$, $k{a}^{n/k}\equiv k{a}^{n/pk}(\mathrm{mod}{p}^r)$. Indeed, let $s=v_p(k)<r$. It suffices to prove $a^{n/k}\equiv a^{n/pk}(\mathrm{mod}{p}^{r-s})$. By the lemma, $a^{p^{r-s}}\equiv a^{p^{r-s-1}}(\mathrm{mod}{p}^{r-s})$. Raising this congruence to the $n/p^{r-s}$-th power yields the result. Thus, $n{z}_n$ satisfies $$n{z}_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(\mathrm{mod}{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),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{array}{rl}\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 _{\begin{array}{c}\frac{m}{dL}\\ \frac{n}{dL}\end{array}}\mu \left(\frac{m}{dL}\right)\\ & =\sum _{dL|n}L{x}_L^d\cdot 1_{\frac{n}{dL}=1}=\sum _{dL=n}L{x}_L^d=\sum _{k|n}k{x}_k^{n/k}.\end{array}$$ 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 }_{[u,v]=n}{A}_u{B}_v$, i.e., the sum over all pairs $(u,v)$ with least common multiple $[u,v]=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.