XVIII математическая олимпиада «Шелковый путь», 2023 год

Пусть $p$ — простое число. Построим ориентированный граф на $p$ вершинах, пронумерованных целыми числами от $0$ до $p - 1$. В графе проводится ребро из вершины $x$ в вершину $y$ тогда и только тогда, когда $y$ равно остатку от деления на $p$ числа $x^2 + 1$. Через $f(p)$ обозначим длину самого длинного ориентированного цикла в этом графе. Докажите, что $f(p)$ может принимать сколь угодно большие значения. ( Зиманов А. )

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

Пусть, $P(x)=x^2+1, P_0(x)=x, P_{n+1}(x)=P(P_n(x))$. Возьмём произвольное нечётное простое число $q$. Заметим, что тогда число $P_q(1)$ - четное и больше двух. Значит, у числа $P_q(1)-1$ есть нечётный простой делитель $p$. Рассмотрим соответствующий граф для числа $p$. Начав с вершины $1$ и пройдясь по ребрам графа $q$ раз мы заново оказываемся в вершине $1$. Значит, длина этого цикла делит $q$. Следовательно, длина этого цикла либо $1$, либо $q$. Очевидно, что длина этого цикла не может быть равна $1$, ведь иначе $2 \equiv 1^2+1 \equiv 1 \pmod{p}$ - противоречие. Значит, в множество значений $f$ входят все нечётные простые, следовательно $f$ может принимать сколь угодно большие значения