Номер 27.46, страница 228 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Глава 5. Основы теории делимости. Параграф 27. Деление с остатком. Сравнения по модулю и их свойства - номер 27.46, страница 228.

Условие.

27.46. Докажите, что для любого натурального числа $n$ найдётся натуральное число, кратное $n$, в десятичной записи которого используются только цифры 1 и 0.

Решение.

Для доказательства этого утверждения воспользуемся принципом Дирихле.

Рассмотрим следующую последовательность из $n+1$ натуральных чисел, состоящих только из цифр 1:

$a_1 = 1$
$a_2 = 11$
$a_3 = 111$
...
$a_{n+1} = \underbrace{11...1}_{n+1 \text{ раз}}$

При делении любого натурального числа на $n$ может получиться $n$ различных остатков: $0, 1, 2, ..., n-1$.

Поскольку в нашей последовательности $n+1$ число, а возможных остатков от деления на $n$ всего $n$, то по принципу Дирихле найдутся как минимум два числа в этой последовательности, которые имеют одинаковый остаток при делении на $n$.

Пусть это будут числа $a_i$ и $a_j$, где $1 \le j < i \le n+1$. Это означает, что $a_i$ и $a_j$ дают одинаковый остаток при делении на $n$, что можно записать в виде сравнения по модулю:

$a_i \equiv a_j \pmod{n}$

Тогда их разность $a_i - a_j$ делится на $n$ нацело. Рассмотрим, как выглядит эта разность:

$a_i - a_j = \underbrace{11...1}_{i \text{ раз}} - \underbrace{11...1}_{j \text{ раз}} = \underbrace{11...1}_{i-j \text{ раз}}\underbrace{00...0}_{j \text{ раз}}$

Например, если $i=5$ и $j=2$, то $a_5 - a_2 = 11111 - 11 = 11100$.

Полученное число $a_i - a_j$ является натуральным, оно кратно $n$, и в его десятичной записи используются только цифры 1 и 0. Таким образом, мы доказали, что для любого натурального числа $n$ найдётся такое число.

Ответ: Утверждение доказано.