Nice problem. I will first give some motivation. Inspect small cases (such as $n=12$ or $8$), with 'smallest' periods $q$, that possibly don't divide $n$ (could be coprime or not). You'll realize that, if you let $d=(q,n)>1$, then $d$ will turn out to be a period, contradicting with minimality of $q$, as $q\nmid n$, $d<q$. Motivated by this, suppose that $n'$ is any period of this function, and $q$ is the smallest period. Suppose $n'=dn_1$ and $q=dq_1$, where $d=(n',q)<q$. I will establish that, $d\mid a-b\implies f(a)=f(b)$, and thus, $d$ is also a period, contradicting with minimality of $q$. To that end, take two numbers, $a_1\equiv a_2\pmod{d}$. I claim that, there exists a $k$, such that $a_1+kq \equiv a_2\pmod{n'}$. For this $k$, the fact that $q$ is a period implies $f(a_1)=f(a_1+kq)$, and the fact that $a_1+kq\equiv a_2\pmod{n'}$ implies $f(a_1+kq)=f(a_2)=f(a_1)$, using the fact that $n'$ is also a period. Now, suppose $a_1-a_2 = \ell d$ for some $\ell\in\mathbb{Z}$. Note that, $a_1+kq\equiv a_2 \pmod{dn_1} \iff \ell d+kdq_1 \equiv 0\pmod{dn_1}$, which holds, if we establish existence of a $k_1$, so that $\ell + kq_1 \equiv 0\pmod{n_1}$. But since $(q_1,n_1)=1$, $q_1^{-1}$ in modulo $n_1$ exists, and thus, it suffices to take, $k\equiv -\ell q_1^{-1}\pmod{n_1}$. Therefore, we are done.

Quote: Nice problem. I will first give some motivation. Inspect small cases (such as $n=12$ or $8$), with 'smallest' periods $q$, that possibly don't divide $n$ (could be coprime or not). You'll realize that, if you let $d=(q,n)>1$, then $d$ will turn out to be a period, contradicting with minimality of $q$, as $q\nmid n$, $d<q$. Motivated by this, suppose that $n'$ is any period of this function, and $q$ is the smallest period. Suppose $n'=dn_1$ and $q=dq_1$, where $d=(n',q)<q$. I will establish that, $d\mid a-b\implies f(a)=f(b)$, and thus, $d$ is also a period, contradicting with minimality of $q$. To that end, take two numbers, $a_1\equiv a_2\pmod{d}$. I claim that, there exists a $k$, such that $a_1+kq \equiv a_2\pmod{n'}$. For this $k$, the fact that $q$ is a period implies $f(a_1)=f(a_1+kq)$, and the fact that $a_1+kq\equiv a_2\pmod{n'}$ implies $f(a_1+kq)=f(a_2)=f(a_1)$, using the fact that $n'$ is also a period. Now, suppose $a_1-a_2 = \ell d$ for some $\ell\in\mathbb{Z}$. Note that, $a_1+kq\equiv a_2 \pmod{dn_1} \iff \ell d+kdq_1 \equiv 0\pmod{dn_1}$, which holds, if we establish existence of a $k_1$, so that $\ell + kq_1 \equiv 0\pmod{n_1}$. But since $(q_1,n_1)=1$, $q_1^{-1}$ in modulo $n_1$ exists, and thus, it suffices to take, $k\equiv -\ell q_1^{-1}\pmod{n_1}$. Therefore, we are done. Actually you have to show that for any $d|a_1-a_2$ there is $dn_1|a_1+kq-a_2$ and $(a_1+kq,n)=1$

grupyorum wrote: Nice problem. I will first give some motivation. Inspect small cases (such as $n=12$ or $8$), with 'smallest' periods $q$, that possibly don't divide $n$ (could be coprime or not). You'll realize that, if you let $d=(q,n)>1$, then $d$ will turn out to be a period, contradicting with minimality of $q$, as $q\nmid n$, $d<q$. Motivated by this, suppose that $n'$ is any period of this function, and $q$ is the smallest period. Suppose $n'=dn_1$ and $q=dq_1$, where $d=(n',q)<q$. I will establish that, $d\mid a-b\implies f(a)=f(b)$, and thus, $d$ is also a period, contradicting with minimality of $q$. To that end, take two numbers, $a_1\equiv a_2\pmod{d}$. I claim that, there exists a $k$, such that $a_1+kq \equiv a_2\pmod{n'}$. For this $k$, the fact that $q$ is a period implies $f(a_1)=f(a_1+kq)$, and the fact that $a_1+kq\equiv a_2\pmod{n'}$ implies $f(a_1+kq)=f(a_2)=f(a_1)$, using the fact that $n'$ is also a period. Now, suppose $a_1-a_2 = \ell d$ for some $\ell\in\mathbb{Z}$. Note that, $a_1+kq\equiv a_2 \pmod{dn_1} \iff \ell d+kdq_1 \equiv 0\pmod{dn_1}$, which holds, if we establish existence of a $k_1$, so that $\ell + kq_1 \equiv 0\pmod{n_1}$. But since $(q_1,n_1)=1$, $q_1^{-1}$ in modulo $n_1$ exists, and thus, it suffices to take, $k\equiv -\ell q_1^{-1}\pmod{n_1}$. Therefore, we are done. I think this solution is imperfect Because you need this property for K too: (n,a1+kq)=1

Guys, I agree with both. Yes, my argument requires a fix, not sure benign or malign. I don't have right now time to try to fix the argument, but you are welcome to do so.

Bump. Not sure if the argument above can be fixed

It's strange that there is no solution to this problem in the official solution.

Here is a complete solution (rephrased from a StackExchange post by Bart Michels): Let $p$ be the minimal period and suppose, for contradiction, that $p$ does not divide $n$. We can then write $n=pq+r$ for some $1 \leq r \leq p-1$. We claim that $r$ must also be a period. To show this, take any $a$ and $b$ coprime with $n$ such that $r\mid a-b$ (if there are no such, i.e. $r\nmid a-b$ always holds, we are done). Then with $a-b=sr$ for some $s$ we obtain $a-b = sn - spq$. Noting that $b$, $a=b+sn-spq$ and hence $b+sn$ are all coprime with $n$, we obtain $f(a) = f(b+sn-spq) = f(b+sn) = f(b)$ (the second equality is because $p$ is a period and the last is because $n$ is a period) - therefore $r$ is also a period, thus contradicting the minimality of $p$. Therefore $p$ divides $n$. What is more, in exactly the same manner (by applying Euclid's algorithm) we have that if $n_0$ is a period, then $\mbox{gcd}(n_0,n)$ is also a period. Now let $k$ be any other period - the problem requires us to prove $p\mid k$. If $k$ does not divide $n$, then by the end of the previous paragraph we may work with $\mbox{gcd}(n,k)$ - and if we show $p\mid \mbox{gcd}(n,k)$ we will also have $p\mid k$ by $\mbox{gcd}(n,k)\mid k$. Hence we may assume that $p$ and $k$ divide $n$. Our aim is to show that $d := \mbox{gcd}(p,k)$ also must be a period - then by the minimality of $p$ we shall have $\mbox{gcd}(p,k) = p$ and we will be done. So let $x$ and $y$ coprime to $n$ be such that $y-x = td$ for some $t$. Then by Bezout's Lemma the inverse $x^{-1} \pmod n$ exists and we have for ANY $u$ and $v$ that $f(x) = f(x + pux) = f((1+pu)x) = f((1+pu)x + kv(1+pu)x) = f((1+pu)(1+kv)x)$ and $f(y) = f(x + td) = f((1 + tdx^{-1})x)$. Since $f$ is $n$ periodic, we will be done if we show that regardless of $t_0 := tx^{-1}$ we can pick $u$ and $v$ such that $1+t_0d \equiv (1+pu)(1+kv) \pmod n$. By the Chinese remainder theorem, it suffices to show that we can find such $u$ and $v$ modulo each maximal prime power divisor $q^s$ of $n$. Fix $q^s$, and let $x,y,z$ be the exponents of $q$ in $p,k,d$. Then $z = \min(x, y)$. By symmetry, we may assume $z = x$. Write $d = q^x \delta$, $p = q^x\alpha$ with $\gcd(\alpha\delta, q) = 1$ and let $\alpha^{-1} \in \mathbb Z$ be an inverse of $\alpha$ mod $q^s$. Then we can take $u = t_0\delta\alpha^{-1}$ and $v = 0$. Indeed: $1 + td = 1 + t \delta q^x \equiv 1+t\delta \alpha^{-1}\alpha q^x \pmod{q^s} = (1+ua)(1+vb)$, as desired.

Rickyminer wrote: It's strange that there is no solution to this problem in the official solution. even in Russian the official solution is empty according to the official results, 5 /95 contestants solved it fully (7/7) (2 from Mongolia and 3 from Bulgaria)

See http://matol.kz/comments/4119/show for a quicker (and I think correct) solution.

Let $a$ and $b$ be two periods. Then for $(a,b)|a_i-a_j$ one can find natural $x,y$ such that $ax+a_j=by+a_i$. Thus $f(ax+a_j-by)=f(a_i) \implies f(a_j)=f(a_i)$. So $(a,b)$ is also a period and we are done.