Остатки и делимость по модулю 7

Пусть в некоторый момент у нас было записано число , где — последняя цифра. Тогда следующее написанное число , то есть остаток от деления числа на не поменялся. Изначально он был равен , но тогда в конце он тоже . Число получиться не могло, поэтому осталась цифра .

Заметим, что числа, номера которых дают одинаковый остаток по модулю дают одинаковый остаток по модулю Поскольку то мы имеем групп с, как минимум, числами и одинаковым остатком по модулю в каждой. Отсюда найдутся две группы с одинаковым остатком (), то есть чисел с таким остатком по модулю будет не менее — чисел с любым остатком по модулю не больше, чем столько, противоречие.

Чтобы доказать делимость произведения на 21, нам нужно доказать делимость на 3 и на 7. Рассматривая таблицу остатков кубов при делении на 7, мы видим, что кубы дают только остатки 0, 1 и 6. Тремя остатками 1 или 6 не получить сумму, делящуюся на 7, поэтому одно из чисел делится на 7.

Аналогично с остатком при делении на 9: кубы дают остатки 0, 1 или 8 при делении на 9. Опять же без остатка 0 не обойтись, ведь тремя числами, дающими остатки 1 или 8, не получить число, делящееся на 9. Значит, один из кубов делится на 9, поэтому и одно из чисел делится на 3.

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

Для имеем

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

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

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

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

Так как число должно делиться на то оно должно делиться на и

делится на при любом выборе поэтому число делится на

По признаку делимости на разность должна делиться на

т.е. должно делиться на

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

Для нахождения достаточно выяснить делимость на числа

1) Делимость на 3 числа возможна в трех случаях:

2) Делимость на 3 числа возможна в трех случаях:

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

Заметим, что среди этих чисел есть два числа, которые дают одинаковый остаток при делении на Пусть это и Тогда получившееся из них число равно

Пронумеруем дни в году, начиная с января. Тогда сумма двух соседних номеров, соответствующих дням, которых идёт речь в условии, должна делиться на Два последовательных числа могут давать такие пары остатков от деления на и и и и и и и Перебором убеждаемся, что единственная пара, удовлетворяющая условию, — это и Так как нумерация началась с понедельника, то искомые дни — среда и четверг.