Областная олимпиада по математике, 2023 год, 10 класс

В графе $G$ вершины пронумерованы числами от 1 до $(p-1)$, где $p>3$ простое. Между любыми двумя вершинами $x$ и $y$ ставится ребро, если существует натуральное $n$, для которого $x^n+y^n$ делится на $p$. Докажите, что в $G$ существует цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу.

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

Лемма. Если $\frac{x}y$ квадратичный невычет, то между вершинами $x, y$ проведено ребро.

Доказательство. По критерию Эйлера для $n=\frac{p-1}2$: $(\frac{x}y)^n\equiv-1\pmod p \Leftrightarrow p|x^n+y^n$.$\square$

Теперь пусть $g$ - первообразный корень по модулю $p$. Тогда цикл, состоящий из последовательно соединённых вершин $g^1,g^2,...,g^{p-1}$ подходит.