Базовый аппарат сравнений по модулю

Заметим, что

Представим остатки полученных от в виде круга остатков. Числа получаются от смещением на или шага по часовой или против часовой стрелки в зависимости от знака.

Заметим, что важен лишь набор , а не их порядок, тогда без ограничения общности выберем пару , — одно из чисел или такое число, которого нет в таблицы. Докажем, что тогда обязательно соседняя с .

Предположим противное, то есть что ни одна пара , не являются соседями (так как иначе можем взять их в качестве , ).

случай (): возьмём (если все различные числа сдвинуть на одинаковое число по модулю , то они останутся одинаковыми, а значит мы можем взять ), в таблицу уже попали числа: , тогда “запрещённые” позиции — (они получены путём прибавления и вычитания , по модулю к полученным клеткам в таблице), а значит, — , но тогда они соседи — противоречие.

случай (): переименуем , в , и получится случай 1.

случай ( аналогично, без ограничения общности, не входит в таблицу): Все остальные числа входят, так как с каждой в таблицу добавляются по 4 числа. Рассмотрим число , у нас уже "запрещены"числа для , иначе входит в таблицу и , иначе в таблице есть повторяющиеся числа, тогда , получается, что , т.е. .

Посмотрим на “запрещённые” числа для : , но снова соседние.

Мы получили, что обязательно должны быть 2 соседних числа. С одной стороны, зачёркнутые ячейки на расстоянии от и образуют место для и (поскольку есть две свободные ячейки вокруг двух зачеркнутых чисел). С другой стороны, при выборе двух , набор двух оставшихся определяется однозначно, поэтому итого вариантов выбора комбинации столько же, сколько и выбор двух подряд идущих чисел в круге, т.е. .