Математикадан облыстық олимпиада, 2023 жыл, 10 сынып

$G$ графының төбелері 1-ден $(p-1)$-ге дейінгі сандармен нөмерленіп шықты, бул жердегі $p>3$ жай сан. Кез келген $x$ және $y$ төбелері үшін, $x^n+y^n$ саны $p$-ға бөлінетіндей $n$ саны табылса, онда сол төбелерді қабырғамен байланыстырамыз. $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}$ подходит.