Областная олимпиада по математике, 2023 год, 10 класс
В графе G вершины пронумерованы числами от 1 до (p−1), где p>3 простое. Между любыми двумя вершинами x и y ставится ребро, если существует натуральное n, для которого xn+yn делится на p. Докажите, что в G существует цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу.
посмотреть в олимпиаде
Комментарий/решение:
Лемма. Если xy квадратичный невычет, то между вершинами x,y проведено ребро.
Доказательство. По критерию Эйлера для n=p−12: (xy)n≡−1(modp)⇔p|xn+yn.◻
Теперь пусть g - первообразный корень по модулю p. Тогда цикл, состоящий из последовательно соединённых вершин g1,g2,...,gp−1 подходит.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.