15-я Международная Жаутыковская олимпиада по математике, 2019 год

Пусть $n > 1$ — натуральное число. Дана функция $f:I \to \mathbb{Z},$ где $I$ — множество всех целых чисел, взаимно простых с $n$. ($\mathbb{Z}$ — множество всех целых чисел). Натуральное число $k$ называется периодом функции $f$ если $f(a)=f(b)$ для любых $a,b\in I$ таких, что $a \equiv b \pmod k$. Известно, что $n$ является периодом функции $f.$ Докажите, что минимальный период функции $f$ делит все ее периоды.
   Пример. Когда $n=6,$ функция $f$ с периодом 6 полностью определяется своими значениями $f(1)$ и $f(5).$ Если $f(1)=f(5),$ то функция имеет минимальный период $P_{\min}=1$, а если $f(1)\ne f(5),$ то $P_{\min}=3.$ ( Е. Байсалов )

Комментарий/решение

Пусть $d_1,d_2$ любые два периода. Докажем, что $d=gcd(d_1,d_2)$ тоже период. Пусть $a\equiv b\pmod d,$ где $a,b\in I.$

Рассмотрим $M\equiv a\pmod{ d_1}$ и $M\equiv b\pmod{d_2}.$ Заменим $lcm(d_1,d_2)=L.$ Докажем, что сущ. $X,$ что $X\equiv M\pmod L$ и $X\in I.$

Заметим, что $gcd(M,d_1,n)=gcd(M,d_2,n)=1\implies$ $gcd(M,L,n)=1.$ Пусть $p_1,\ldots$ все простые, что $p_i\mid n,$ но $p_i\nmid L.$

Далее рассмотрим систему сравнений (по К.Т.О. она имеет решение):

$X\equiv M\pmod L$

$X\equiv 1\pmod {p_i}\ \forall i$

Легко вывести, что $X\in I.$ Тогда $f(a)=f(X)=f(b),$ так как $X\equiv a\pmod {d_1}$ и $X\equiv b\pmod {d_2}.\quad\square$