International Zhautykov Olympiad 2019 problem 5 
Natural number $n>1$ is given. Let $I$ be the set of integers that are relatively prime to $n$. Define a function $f:I\to\mathbb Z$. We call a function $k$-periodic if for any $a,b\in I$, $f(a)=f(b)$ whenever $k\mid a-b $. We know that $f$ is $n$-periodic. Prove that minimal period of $f$ divides all other periods.
Example: if $n=6$ and $f(1)=f(5)$ then minimal period is $1$, if $f(1)$ is not equal to $f(5)$ then minimal period is $3$.

There is no official solution to this problem, see here, which means it is really difficult, so I hope to solve it here. Thank you.
 A: Let $p$ be the minimal period of $f$ (for the order relation on $\mathbb Z$) and $k$ be any period. We want to show that $p \mid k$.
Step 1: reduction to $p, k \mid n$.
Lemma 1. If $c$ is any period and $r$ is the remainder when $n$ is divided by $c$. Then $r$ is a period.
Using the lemma, we find that:


*

*The minimal period $p$ divides $n$.

*When $k$ does not divide $n$, let $r$ be the remainder when $n$ is divided by $k$. Then $r$ is a period, and it suffices to show that $p$ divides $r$. If $r \nmid n$, we proceed and let $r_1$ be the remainder when $n$ is divided by $r_1$. It suffices to show that $p \mid r_1$. And so on: by induction on $k$ we may assume that $k \mid n$.


Proof of lemma 1. Write $n = qc+r$ and let $a,b \in \mathbb Z$ be coprime with $n$ and such that we can write $a-b = dr$. Then $a-b = dn - dqc$ so
$$f(a) = f(b+dn-dqc) = f(b+qc) = f(b)$$
where we have to remark that all those arguments are indeed coprime with $n$. $\square$
Step 2: The case $p, k \mid n$.
Lemma 2. Let $a,b \mid n$ with $\gcd(a,b) = d$. Then for each $t \in \mathbb Z$ there exist $u,v,w \in \mathbb Z$ with
$$1+td = (1+ua)(1+vb) + wn$$
(Alternative form: Let $a, b \mid n$ with $\gcd(a,b) = d$. For a divisor $m \mid n$, denote by $K_m$ the kernel of the surjective reduction map
$$\pi_m : (\mathbb Z/n)^{\times} \twoheadrightarrow (\mathbb Z/m)^{\times}$$
Then $K_aK_b = K_d$.)
We apply the lemma with $(a,b) = (p,k)$ and show that $d$ is a period of $f$, so that we must have $d = p$. Let $x,y \in \mathbb Z$ be coprime to $n$ and such that $d \mid x-y$, say $y = x+td$. We want to show that $f(x) = f(y)$. Let $x^{-1} \in \mathbb Z$ be a fixed inverse of $x$ mod $n$. We have $y \equiv x \cdot (1+d tx^{-1}) \pmod n$. Let $1+ua, 1+vb, w \in \mathbb Z$ be such that
$$1+d tx^{-1} = (1+ua)(1+vb) + wn$$
Then $$f(x) = f((1+ua)x) = f((1+vb)(1+ua)x) = f((1+d tx^{-1})x - wnx) = f(y)$$
because $f$ is $a$-periodic, $b$-periodic and $n$-periodic.
Proof of lemma 2. We want to show that there exist $u,v \in \mathbb Z$ with
$$1+td \equiv (1+ua)(1+vb) \pmod n$$
That is, for each $p^s \Vert n$, $1+td \equiv (1+ua)(1+vb) \pmod{p^s}$. By the Chinese remainder theorem, it suffices to show that we can find such $u$ and $v$ modulo each $p^s$. Fix $p^s$, and let $x,y,z$ be the exponents of $p$ in $a,b,d$. Then $z = \min(x, y)$. By symmetry, we may assume $z = x$. Write $d = p^x \delta$, $a = p^x\alpha$ with $\gcd(\alpha\delta, p) = 1$ and let $\alpha^{-1} \in \mathbb Z$ be a fixed inverse of $\alpha$ mod $p^s$. Then we can take $u = t\delta\alpha^{-1}$ and $v = 0$. Indeed:
$$\begin{align*}
1 + td
&= 1 + t \delta p^x \\
&\equiv 1+t\delta \alpha^{-1}\alpha p^x \pmod{p^s} \\
&= (1+ua)(1+vb)
\end{align*}$$
(Proof of alternative form: The Chinese remainder theorem gives an isomorphism
$$\phi : (\mathbb Z/n)^{\times} \to \prod_{p^s \Vert n} (\mathbb Z/p^s)^\times $$
We have that '$\phi$ commutes with the $\pi_m$' and so it suffices to do the case where $n$ is a prime power. In that case, either $a \mid b$ or $b \mid a$, and the equality $K_aK_b = K_d$ is trivial. $\square$)
