Задача 3. Остатки Пети и Васи

Предположим, что оба правы

Будем доказывать от противного. Пусть никто не ошибся: есть число $N$, которое при делении на $31, 32, 33, 34$ даёт остатки $1, 4, 7, 10$ в каком-то порядке, а при делении на $85, 86, 87, 88$ — остатки $1, 2, 5, 8$ в каком-то порядке.

«В некотором порядке» значит: четыре деления дали ровно эти четыре остатка, каждый по одному разу. Например, остаток $1$ у Пети получился ровно при одном делении.

Какой остаток к какому делению относится, мы не знаем, а расстановок много: $24\cdot 24 = 576$. Перебирать их не будем — поищем деления, которые можно сравнить между собой.

Общий множитель связывает остатки

Пусть $N$ при делении на $33$ даёт остаток $r$, то есть $N = 33q + r$. Так как $33 = 3\cdot 11$,

Число $11\cdot(3q)$ делится на $11$. Если ещё и $r < 11$, то $r$ — это и остаток от деления $N$ на $11$: из $N$ вычли целое число раз по $11$, и осталось меньше $11$.

Например, $106 = 33\cdot 3 + 7$, и $106 = 11\cdot 9 + 7$: остаток $7$ при делении на $33$ остаётся остатком $7$ и при делении на $11$. Так остаток от деления на число подсказывает остаток от деления на его множитель.

Сравним деления на 33 и на 88

Какие деления Пети и Васи можно так сравнить? Разложим делители на множители:

• у Пети: $31$ — простое число, $32 = 2^5$, $33 = 3\cdot 11$, $34 = 2\cdot 17$;

• у Васи: $85 = 5\cdot 17$, $86 = 2\cdot 43$, $87 = 3\cdot 29$, $88 = 8\cdot 11$.

Общий множитель больше $2$ есть у пар $33$ и $88$ (это $11$), $34$ и $85$ ($17$), $32$ и $88$ ($8$), $33$ и $87$ ($3$); кроме того, все чётные делители делятся на $2$. Удобнее всего множители $11$ и $17$: они больше всех остатков, и тогда, как в шаге 2, остатки в паре просто обязаны совпасть. С меньшими множителями пришлось бы сравнивать остатки остатков, а для доказательства хватит пар с $11$ и $17$.

Начнём с пары $33 = 3\cdot 11$ и $88 = 8\cdot 11$: оба числа делятся на $11$. Остаток Пети при делении на $33$ — одно из чисел $1, 4, 7, 10$. Все они меньше $11$, поэтому это и есть остаток $N$ при делении на $11$. Остаток Васи при делении на $88$ — одно из чисел $1, 2, 5, 8$, тоже меньше $11$, и это тоже остаток $N$ при делении на $11$.

Но у числа $N$ только один остаток при делении на $11$. Значит, Петин остаток при делении на $33$ равен Васиному при делении на $88$ — это число есть в обоих наборах. Общее у наборов $1, 4, 7, 10$ и $1, 2, 5, 8$ только одно — $1$. Итак, при делении на $33$ у Пети остаток $1$.

Сравним деления на 34 и на 85

Ещё одна такая пара: $34 = 2\cdot 17$ у Пети и $85 = 5\cdot 17$ у Васи — оба делятся на $17$.

Все остатки обоих мальчиков меньше $17$. Поэтому, как и в шаге 3, Петин остаток при делении на $34$ — это остаток $N$ при делении на $17$, и Васин остаток при делении на $85$ — тоже он. Они равны, а общее у наборов снова только $1$. Итак, при делении на $34$ у Пети тоже остаток $1$.

Противоречие

Получилось, что у Пети остаток $1$ и при делении на $33$, и при делении на $34$. Но среди его остатков $1, 4, 7, 10$ единица одна — одно из этих двух делений должно было дать другой остаток. Значит, записи Пети и Васи не могут быть верны вместе: кто-то из них ошибся.

Заметь: по отдельности каждый мог и не ошибиться. У Пети всё сходится при $N = 103$:

Ошибку видно, только если сравнить записи обоих мальчиков.

Второй вариант

Идея та же — ищем пары делителей с общим множителем. Но во второй паре остатки уже больше общего множителя, и сравнивать придётся остатки остатков.

Пара $44$ и $88$. $88 = 2\cdot 44$, поэтому, как в шаге 2, Васин остаток при делении на $88$ — одно из $1, 4, 6, 7$, все меньше $44$, — это и остаток $N$ при делении на $44$, то есть Петин остаток при делении на $44$ — одно из $1, 2, 3, 8$. Общее у наборов только $1$: у Пети при делении на $44$ остаток $1$.

Пара $42$ и $90$. $42 = 7\cdot 6$ и $90 = 15\cdot 6$ — оба делятся на $6$. Но здесь остатки бывают и не меньше $6$, поэтому рассуждение шага 2 нужно чуть продолжить. Пусть $N = 42q + r$, и пусть сам остаток $r$ при делении на $6$ даёт остаток $s$: $r = 6t + s$, где $s < 6$. Тогда

поэтому остаток $N$ при делении на $6$ равен $s$ — остатку от деления на $6$ самого $r$. Например, $50 = 42\cdot 1 + 8$ и $8 = 6\cdot 1 + 2$, поэтому $50 = 6\cdot 8 + 2$. Так же и с делением на $90 = 15\cdot 6$. Значит, остаток $N$ при делении на $6$ равен остатку от деления на $6$ и Петиного остатка при делении на $42$, и Васиного остатка при делении на $90$.

Петины $1, 2, 3, 8$ дают при делении на $6$ остатки $1, 2, 3, 2$ (ведь $8 = 6 + 2$), Васины $1, 4, 6, 7$ — остатки $1, 4, 0, 1$. Совпасть может только $1$, а у Пети её даёт только сам остаток $1$: у Пети при делении на $42$ тоже остаток $1$.

Противоречие. Единица у Пети одна, а нужна и при делении на $44$, и при делении на $42$. Значит, кто-то ошибся.

Отличия от первого варианта: первая пара связана сильнее — $88$ делится на $44$ целиком; во второй паре остатки больше общего множителя $6$, поэтому сначала находим их остатки при делении на $6$. По отдельности оба снова могли быть правы: Петя — при $N = 285\,650$, Вася — при $N = 1\,441\,356$. Перебор всех $576$ расстановок второго варианта тоже не нашёл ни одной подходящей.