22-ші «Жібек жолы» математикалық олимпиадасы, 2023 жыл

$p$ саны — жай сан. $p$ төбесі бар (әр төбесі $0$-ден ${p - 1}$-ге дейін нөмірленген) бағытталған графты салайық. Егер $x^2 + 1$ санын $p$-ға бөлгенде қалдық $y$ санына тең болса, онда осы графта $x$ төбесін $y$ төбесімен қабырғамен қосамыз (басқа жағдайда $x$ және $y$ төбелерін қабырғамен қосуға болмайды). $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$ может принимать сколь угодно большие значения