Китайская теорема об остатках

Заметим, что даёт только остатки по модулю для соответственно.

Для имеем

По условию нам нужно

В качестве примера рассмотрим . Здесь накладываются два условия . Уместно воспользоваться Китайской теоремой об остатках, которая говорит нам, что таких чисел будет ровно два в наборе , но можно и явно найти эти числа — . Здесь легко видеть, что от сдвига набора ничего не поменяется, поскольку нам важно только наличие всех остатков по модулю ровно по одному разу.

Абсолютно аналогично по два числа в каждом наборе из подряд идущего подойдут для остатков и , то есть в итоге из каждых нам подойдут чисел.

Поскольку , то из первых групп подойдут . Остаются числа чисел , из которых подходит . Получаем ответ