Страница 367 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

47.29. Сумма остатков при делении натурального числа $\textit{n}$ на числа 3, 6 и 9 равна 15. Найдите эти остатки.

Пусть $r_3$, $r_6$ и $r_9$ — это остатки от деления натурального числа $n$ на 3, 6 и 9 соответственно.

По определению остатка от деления, мы имеем следующие ограничения на возможные значения остатков:
Остаток при делении на 3: $0 \le r_3 < 3$. Таким образом, максимально возможное значение для $r_3$ равно 2.
Остаток при делении на 6: $0 \le r_6 < 6$. Таким образом, максимально возможное значение для $r_6$ равно 5.
Остаток при делении на 9: $0 \le r_9 < 9$. Таким образом, максимально возможное значение для $r_9$ равно 8.

По условию задачи, сумма этих остатков равна 15:
$r_3 + r_6 + r_9 = 15$.

Теперь найдем максимально возможную сумму остатков, сложив их максимальные значения:
Максимальная сумма = $2 + 5 + 8 = 15$.

Поскольку сумма остатков по условию равна 15, что в точности совпадает с максимально возможной суммой, то это возможно только в одном случае: когда каждый из остатков равен своему максимальному значению.
Следовательно, остаток при делении на 3 равен 2, остаток при делении на 6 равен 5, и остаток при делении на 9 равен 8.

Для полноты решения убедимся, что такое натуральное число $n$ существует. Например, для числа $n=17$:
$17$ при делении на $3$ дает остаток $2$ ($17 = 3 \times 5 + 2$).
$17$ при делении на $6$ дает остаток $5$ ($17 = 6 \times 2 + 5$).
$17$ при делении на $9$ дает остаток $8$ ($17 = 9 \times 1 + 8$).
Сумма остатков $2+5+8=15$. Условия задачи выполняются, значит, найденные значения остатков верны.

Ответ: остаток при делении на 3 равен 2, на 6 — 5, на 9 — 8.

47.30. Докажите, что среди чисел вида $4^n + 4^m$ ($m$ и $n$ — натуральные числа) нет ни одного квадрата натурального числа.

Для доказательства того, что среди чисел вида $4^n + 4^m$ (где $m$ и $n$ – натуральные числа) нет ни одного квадрата натурального числа, рассмотрим два возможных случая.

Случай 1: $m = n$

В этом случае выражение принимает вид:$4^n + 4^n = 2 \cdot 4^n = 2 \cdot (2^2)^n = 2 \cdot 2^{2n} = 2^{2n+1}$. Число является полным квадратом тогда и только тогда, когда в его разложении на простые множители все показатели степеней являются четными. В нашем случае простой множитель 2 входит в разложение в степени $2n+1$. Поскольку $n$ – натуральное число, $2n+1$ всегда является нечетным числом. Следовательно, число $2^{2n+1}$ не может быть квадратом натурального числа.

Случай 2: $m \neq n$

Без ограничения общности, предположим, что $m < n$. Тогда $n-m$ является натуральным числом. Обозначим $d = n-m$, где $d \geq 1$. Преобразуем исходное выражение, вынеся за скобки общий множитель $4^m$:$4^m + 4^n = 4^m(1 + 4^{n-m}) = 4^m(1 + 4^d)$. Заметим, что $4^m = (2^m)^2$ уже является полным квадратом. Чтобы произведение $4^m(1 + 4^d)$ было полным квадратом, необходимо, чтобы и второй множитель, $(1 + 4^d)$, также был полным квадратом.

Допустим, что $1 + 4^d$ является квадратом некоторого натурального числа $k$. То есть, $1 + 4^d = k^2$. Перепишем это уравнение:$4^d = k^2 - 1$$(2^d)^2 = (k-1)(k+1)$

Произведение двух чисел $(k-1)$ и $(k+1)$ является степенью двойки. Это означает, что каждое из этих чисел также должно быть степенью двойки. Пусть $k-1 = 2^a$ и $k+1 = 2^b$, где $a$ и $b$ – целые неотрицательные числа, и $b > a$.

Вычтем первое уравнение из второго:$(k+1) - (k-1) = 2^b - 2^a$$2 = 2^b - 2^a$$2 = 2^a(2^{b-a} - 1)$

Поскольку $d \ge 1$, то $k^2 = 1 + 4^d \ge 1+4=5$. Отсюда $k$ – натуральное число, большее 2, а значит $k-1 \ge 2$. Тогда $2^a = k-1 \ge 2$, что означает $a \ge 1$. Из уравнения $2 = 2^a(2^{b-a} - 1)$ следует, что $2^a$ должно быть делителем числа 2. Единственный делитель, который не меньше 2, это 2. Следовательно, $2^a=2$, что дает $a=1$.

Подставив $a=1$ в уравнение $2 = 2^a(2^{b-a} - 1)$, получаем:$2 = 2(2^{b-1} - 1)$$1 = 2^{b-1} - 1$$2 = 2^{b-1}$Отсюда $b-1=1$, что означает $b=2$.

Итак, единственно возможное решение — это $a=1$ и $b=2$. Это соответствует $k-1 = 2^1 = 2$, то есть $k=3$. Подставим это значение в наше предположение $1 + 4^d = k^2$:$1 + 4^d = 3^2 = 9$$4^d = 8$$(2^2)^d = 2^3$$2^{2d} = 2^3$$2d = 3$$d = 1.5$

Однако мы определили $d = n-m$ как натуральное число. Полученное значение $d=1.5$ не является натуральным числом, что приводит к противоречию. Следовательно, наше предположение о том, что $1 + 4^d$ может быть полным квадратом, неверно.

Таким образом, ни в одном из случаев ($m=n$ или $m \neq n$) число вида $4^n + 4^m$ не может быть квадратом натурального числа, что и требовалось доказать.

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

47.31. Докажите, что среди чисел вида $5^n + 5^m$ ($m$ и $n$ — натуральные числа) нет ни одного квадрата натурального числа.

а)

Требуется доказать, что число вида $5^n + 5^m$, где $m$ и $n$ — натуральные числа, не может быть квадратом натурального числа. Обозначим данное число как $A = 5^n + 5^m$. Предположим от противного, что $A$ является полным квадратом, то есть $A = k^2$ для некоторого натурального числа $k$.

Не нарушая общности, предположим, что $n \le m$. Рассмотрим два возможных случая.

Случай 1: $n = m$.

В этом случае выражение для $A$ принимает вид: $A = 5^n + 5^n = 2 \cdot 5^n$. Для того чтобы число было полным квадратом, все показатели степеней в его разложении на простые множители должны быть четными. В разложении числа $A = 2^1 \cdot 5^n$ на простые множители множитель $2$ имеет показатель степени $1$, что является нечетным числом. Следовательно, $A$ не может быть квадратом натурального числа.

Случай 2: $n < m$.

Вынесем за скобки $5^n$: $A = 5^n(1 + 5^{m-n})$. Пусть $d = m - n$. Поскольку $m$ и $n$ — натуральные числа и $n < m$, то $d$ также является натуральным числом ($d \ge 1$). Тогда $A = 5^n(1 + 5^d)$.

По нашему предположению, $A = k^2$, следовательно, $5^n(1 + 5^d) = k^2$. Рассмотрим множители $5^n$ и $(1 + 5^d)$. Число $5^n$ делится на 5 (так как $n \ge 1$). Число $1 + 5^d$ при делении на 5 дает в остатке 1, значит, оно не делится на 5. Таким образом, числа $5^n$ и $(1 + 5^d)$ не имеют общих делителей, кроме 1, то есть они взаимно просты.

Известно, что если произведение двух взаимно простых чисел является полным квадратом, то каждое из этих чисел само по себе должно быть полным квадратом. Отсюда следует, что должны одновременно выполняться два условия:
1) $5^n$ — полный квадрат.
2) $1 + 5^d$ — полный квадрат.

Для выполнения первого условия необходимо, чтобы показатель степени $n$ был четным числом. Это возможно.

Рассмотрим второе условие. Пусть $1 + 5^d = s^2$ для некоторого натурального числа $s$. Тогда $5^d = s^2 - 1$. Разложим правую часть по формуле разности квадратов: $5^d = (s-1)(s+1)$. Так как $5$ — простое число, а $(s-1)$ и $(s+1)$ — целые числа, то каждый из этих множителей должен быть степенью числа 5. Пусть $s-1 = 5^x$ и $s+1 = 5^y$, где $x$ и $y$ — целые неотрицательные числа.

Поскольку $s+1 > s-1$, должно выполняться неравенство $y > x$. Найдем разность этих двух выражений: $(s+1) - (s-1) = 2$ $5^y - 5^x = 2$ Вынесем $5^x$ за скобки: $5^x(5^{y-x} - 1) = 2$.

Так как $x$ — целое неотрицательное число, $5^x$ является делителем числа 2. Единственная степень пятерки, которая является делителем 2, — это $5^0 = 1$. Следовательно, $x=0$.

Подставим $x=0$ в уравнение $5^x(5^{y-x} - 1) = 2$: $5^0(5^{y-0} - 1) = 2$ $1 \cdot (5^y - 1) = 2$ $5^y - 1 = 2$ $5^y = 3$. Это уравнение не имеет решений в целых числах $y$. Мы получили противоречие.

Это означает, что наше предположение о том, что $1 + 5^d$ может быть полным квадратом, неверно. Следовательно, и во втором случае число $A$ не является квадратом натурального числа.

Поскольку ни в одном из случаев число вида $5^n + 5^m$ не может быть квадратом натурального числа, исходное утверждение доказано.

Ответ: Доказано, что среди чисел вида $5^n + 5^m$ (m и n — натуральные числа) нет ни одного квадрата натурального числа.

47.32. О числах $m, n, p, q, r$ и $s$ известно, что $m^2 + n^2 + p^2 + q^2 + r^2 = s^2$.

Докажите, что хотя бы одно из этих чисел чётное.

Для доказательства воспользуемся методом от противного. Предположим, что все шесть чисел — $m, n, p, q, r, s$ — являются нечётными.

Рассмотрим, какой остаток даёт квадрат нечётного числа при делении на 8.

Любое нечётное число $k$ можно представить в виде $k = 2a + 1$, где $a$ — целое число. Тогда его квадрат равен:$k^2 = (2a + 1)^2 = 4a^2 + 4a + 1 = 4a(a+1) + 1$.

Произведение двух последовательных целых чисел $a(a+1)$ всегда является чётным, то есть $a(a+1) = 2b$ для некоторого целого $b$. Подставив это в выражение для $k^2$, получим:$k^2 = 4(2b) + 1 = 8b + 1$.

Это означает, что квадрат любого нечётного числа при делении на 8 даёт в остатке 1. В терминах сравнений по модулю это можно записать как $k^2 \equiv 1 \pmod{8}$.

Теперь вернёмся к исходному уравнению: $m^2 + n^2 + p^2 + q^2 + r^2 = s^2$. Рассмотрим это уравнение по модулю 8.

Так как по нашему предположению все числа $m, n, p, q, r, s$ нечётные, то квадраты каждого из них сравнимы с 1 по модулю 8.

Левая часть уравнения:$m^2 + n^2 + p^2 + q^2 + r^2 \equiv 1 + 1 + 1 + 1 + 1 \pmod{8}$$m^2 + n^2 + p^2 + q^2 + r^2 \equiv 5 \pmod{8}$

Правая часть уравнения:$s^2 \equiv 1 \pmod{8}$

Таким образом, мы приходим к сравнению $5 \equiv 1 \pmod{8}$, что является неверным.

Полученное противоречие означает, что наше первоначальное предположение о том, что все шесть чисел нечётные, было неверным. Следовательно, хотя бы одно из чисел $m, n, p, q, r, s$ должно быть чётным.

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

47.33. Остаток при делении трёхзначного числа $n = \overline{aa5}$ на некоторое однозначное число равен 8. Найдите число $n$.

Пусть $n$ — искомое трёхзначное число, а $d$ — некоторый однозначный делитель.

По условию, число $n$ имеет вид $\overline{aa5}$. Это означает, что первая и вторая цифры числа одинаковы и равны $a$, а третья цифра равна 5. Запишем это число в виде суммы разрядных слагаемых:

$n = 100 \cdot a + 10 \cdot a + 5 = 110a + 5$.

Поскольку $n$ — трёхзначное число, его первая цифра $a$ не может быть нулём. Таким образом, $a$ — это цифра от 1 до 9.

Также по условию, остаток от деления числа $n$ на $d$ равен 8. Известно, что остаток от деления всегда меньше делителя. Следовательно, делитель $d$ должен быть больше остатка 8:

$d > 8$.

Так как $d$ — это однозначное число (от 1 до 9), единственное возможное значение для $d$, удовлетворяющее условию $d > 8$, — это $d=9$.

Теперь мы знаем, что число $n$ при делении на 9 даёт в остатке 8. Это можно записать в виде сравнения по модулю:

$n \equiv 8 \pmod{9}$.

Подставим в это сравнение выражение для $n$:

$110a + 5 \equiv 8 \pmod{9}$.

Вычтем 5 из обеих частей сравнения:

$110a \equiv 3 \pmod{9}$.

Упростим коэффициент при $a$. Найдём остаток от деления 110 на 9:

$110 = 12 \cdot 9 + 2$.

Следовательно, $110 \equiv 2 \pmod{9}$. Заменим 110 на 2 в нашем сравнении:

$2a \equiv 3 \pmod{9}$.

Нам нужно найти такую цифру $a$ (от 1 до 9), что $2a$ при делении на 9 даёт в остатке 3. Переберём возможные значения $a$:

• Если $a=1$, то $2 \cdot 1 = 2 \equiv 2 \pmod{9}$.
• Если $a=2$, то $2 \cdot 2 = 4 \equiv 4 \pmod{9}$.
• Если $a=3$, то $2 \cdot 3 = 6 \equiv 6 \pmod{9}$.
• Если $a=4$, то $2 \cdot 4 = 8 \equiv 8 \pmod{9}$.
• Если $a=5$, то $2 \cdot 5 = 10 \equiv 1 \pmod{9}$.
• Если $a=6$, то $2 \cdot 6 = 12 \equiv 3 \pmod{9}$. Это значение нам подходит.
• Если $a=7$, то $2 \cdot 7 = 14 \equiv 5 \pmod{9}$.
• Если $a=8$, то $2 \cdot 8 = 16 \equiv 7 \pmod{9}$.
• Если $a=9$, то $2 \cdot 9 = 18 \equiv 0 \pmod{9}$.

Единственное подходящее значение для $a$ — это 6.

Теперь найдём число $n$, подставив $a=6$ в его формулу $\overline{aa5}$:

$n = 665$.

Проверим результат: разделим 665 на 9.

$665 = 9 \cdot 73 + 8$.

Остаток действительно равен 8. Условие задачи выполнено.

Ответ: 665.

47.34. Остаток при делении трёхзначного числа $m = \overline{2bb}$ на некоторое однозначное число равен 8. Найдите число $m$.

Пусть $m$ — искомое трёхзначное число, а $n$ — некоторый однозначный делитель. По условию, число $m$ имеет вид $\overline{2bb}$, где $b$ — это цифра от 0 до 9. В виде алгебраической суммы это число можно записать так: $m = 2 \cdot 100 + b \cdot 10 + b = 200 + 11b$.

Из условия задачи известно, что при делении числа $m$ на однозначное число $n$ остаток равен 8. В теории чисел существует правило: остаток от деления всегда должен быть строго меньше делителя. Следовательно, делитель $n$ должен быть больше остатка 8, то есть $n > 8$.

Поскольку $n$ — это однозначное число (т.е. $n \in \{1, 2, ..., 9\}$), единственным возможным значением для $n$, которое больше 8, является 9. Таким образом, делитель $n=9$.

Теперь мы знаем, что число $m$ при делении на 9 даёт в остатке 8. Это можно записать с помощью сравнения по модулю: $m \equiv 8 \pmod{9}$.

Для решения воспользуемся свойством сравнений и признаком делимости на 9: число даёт такой же остаток при делении на 9, как и сумма его цифр. Сумма цифр числа $m = \overline{2bb}$ равна $2 + b + b = 2 + 2b$. Следовательно, сумма цифр числа $m$ также должна давать остаток 8 при делении на 9: $2 + 2b \equiv 8 \pmod{9}$.

Решим полученное сравнение относительно $b$: $2b \equiv 8 - 2 \pmod{9}$ $2b \equiv 6 \pmod{9}$.

Нам нужно найти такую цифру $b$ (от 0 до 9), которая удовлетворяет этому условию. Проверим значения $b$ по порядку. При $b=0$, $2 \cdot 0 = 0 \not\equiv 6 \pmod{9}$. При $b=1$, $2 \cdot 1 = 2 \not\equiv 6 \pmod{9}$. При $b=2$, $2 \cdot 2 = 4 \not\equiv 6 \pmod{9}$. При $b=3$, $2 \cdot 3 = 6$, что удовлетворяет сравнению $6 \equiv 6 \pmod{9}$. Таким образом, мы нашли подходящее значение $b=3$. Дальнейшая проверка показывает, что среди цифр от 4 до 9 других решений нет. Единственное решение — $b=3$.

Зная значение $b$, находим искомое число $m$: $m = \overline{2bb} = 233$.

Проверим полученный результат: разделим 233 на 9. $233 = 9 \cdot 25 + 8$. Деление даёт частное 25 и остаток 8, что полностью соответствует условию задачи.

Ответ: 233.

47.35. При делении натурального числа $n$ на 9 остаток равен неполному частному, при делении $n$ на 14 остаток также равен неполному частному. Найдите все возможные значения $n$.

Согласно условию, при делении натурального числа $n$ на 9 неполное частное равно остатку. Обозначим неполное частное и остаток как $q_1$. По определению деления с остатком, мы можем записать:$n = 9 \cdot q_1 + q_1$$n = 10 \cdot q_1$При делении на 9 остаток $q_1$ должен удовлетворять неравенству $0 \le q_1 < 9$. Поскольку $n$ — натуральное число, $n > 0$, значит $q_1$ должно быть целым положительным числом. Таким образом, возможные значения для $q_1$: $1, 2, 3, 4, 5, 6, 7, 8$.

Аналогично, при делении натурального числа $n$ на 14 неполное частное равно остатку. Обозначим неполное частное и остаток как $q_2$. Это можно записать в виде уравнения:$n = 14 \cdot q_2 + q_2$$n = 15 \cdot q_2$При делении на 14 остаток $q_2$ должен удовлетворять неравенству $0 \le q_2 < 14$. Поскольку $n$ — натуральное число, $q_2$ также должно быть целым положительным числом. Таким образом, возможные значения для $q_2$: $1, 2, ..., 13$.

Так как оба выражения представляют одно и то же число $n$, мы можем их приравнять:$10 \cdot q_1 = 15 \cdot q_2$Разделим обе части уравнения на 5:$2 \cdot q_1 = 3 \cdot q_2$

Из этого равенства следует, что $2 \cdot q_1$ должно быть кратно 3. Так как 2 и 3 являются взаимно простыми числами, $q_1$ должно быть кратно 3. Учитывая возможные значения для $q_1$ (от 1 до 8), выберем те, которые кратны 3:$q_1 = 3$ или $q_1 = 6$.

Рассмотрим каждый из этих случаев:1. Если $q_1 = 3$, то $n = 10 \cdot 3 = 30$. Найдем соответствующее значение $q_2$:$2 \cdot 3 = 3 \cdot q_2 \implies 6 = 3 \cdot q_2 \implies q_2 = 2$. Значение $q_2=2$ находится в допустимом диапазоне (от 1 до 13). Следовательно, $n = 30$ является решением. Проверка: $30 \div 9 = 3$ (ост. 3); $30 \div 14 = 2$ (ост. 2). Условия выполняются.

2. Если $q_1 = 6$, то $n = 10 \cdot 6 = 60$. Найдем соответствующее значение $q_2$:$2 \cdot 6 = 3 \cdot q_2 \implies 12 = 3 \cdot q_2 \implies q_2 = 4$. Значение $q_2=4$ также находится в допустимом диапазоне (от 1 до 13). Следовательно, $n = 60$ является решением. Проверка: $60 \div 9 = 6$ (ост. 6); $60 \div 14 = 4$ (ост. 4). Условия выполняются.

Следующее возможное значение для $q_1$, кратное 3, это 9, но оно выходит за пределы допустимого диапазона $1 \le q_1 \le 8$. Таким образом, других решений нет.

Ответ: 30, 60.

47.36. Докажите, что среди натуральных степеней числа 2 существуют две такие, что их разность кратна числу 1001.

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

Рассмотрим последовательность, состоящую из 1002 различных натуральных степеней числа 2:

$2^1, 2^2, 2^3, \ldots, 2^{1002}$

Теперь рассмотрим остатки от деления каждого члена этой последовательности на число 1001. При делении любого целого числа на 1001 существует 1001 возможный остаток: $0, 1, 2, \ldots, 1000$.

Таким образом, у нас есть 1002 числа (степени двойки) и 1001 возможный вариант для остатка. Согласно принципу Дирихле, если число объектов (в нашем случае, 1002) больше числа возможных категорий (1001), то как минимум два объекта должны попасть в одну и ту же категорию.

Это означает, что в нашей последовательности найдутся по крайней мере две различные степени, обозначим их $2^m$ и $2^n$ (где $m$ и $n$ — натуральные числа, и для определенности пусть $m > n$), которые имеют одинаковый остаток при делении на 1001.

Этот факт можно записать в виде сравнения по модулю:

$2^m \equiv 2^n \pmod{1001}$

По определению сравнения, это означает, что разность $(2^m - 2^n)$ делится на 1001 нацело, то есть является кратной числу 1001.

Следовательно, мы доказали, что среди натуральных степеней числа 2 существуют две такие, что их разность кратна числу 1001. Что и требовалось доказать.

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

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

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

$a_1 = 1$

$a_2 = 11$

$a_3 = 111$

...

$a_n = \underbrace{11\dots1}_{n \text{ раз}}$

Теперь рассмотрим остатки от деления этих $n$ чисел на данное натуральное число $n$. Пусть $r_k$ — это остаток от деления числа $a_k$ на $n$, то есть $r_k = a_k \pmod n$. Мы получим $n$ остатков: $r_1, r_2, \dots, r_n$.

При делении на $n$ существует ровно $n$ возможных остатков: $0, 1, 2, \dots, n-1$.

Далее возможны два случая:

Случай 1: Один из остатков равен нулю.

Пусть для некоторого $k$ (где $1 \le k \le n$) остаток $r_k = 0$. Это означает, что число $a_k$ делится на $n$ нацело. Число $a_k$ состоит только из цифр 1, что удовлетворяет условию (в его записи используются только цифры 1 и 0). Следовательно, в этом случае число $a_k$ является искомым.

Случай 2: Ни один из остатков не равен нулю.

Если ни один из остатков $r_1, r_2, \dots, r_n$ не равен 0, то все эти $n$ остатков принимают значения из множества $\{1, 2, \dots, n-1\}$. В этом множестве всего $n-1$ различный элемент. Поскольку у нас есть $n$ остатков, а возможных значений для них только $n-1$, то по принципу Дирихле как минимум два остатка должны быть одинаковыми. Пусть $r_i = r_j$ для некоторых $i$ и $j$ таких, что $1 \le i < j \le n$.

Равенство остатков $r_i = r_j$ означает, что $a_j \equiv a_i \pmod n$. Отсюда следует, что их разность $(a_j - a_i)$ кратна $n$. Рассмотрим это число $M = a_j - a_i$.

$M = \underbrace{11\dots1}_{j \text{ раз}} - \underbrace{11\dots1}_{i \text{ раз}} = \underbrace{11\dots1}_{j-i \text{ раз}}\underbrace{00\dots0}_{i \text{ раз}}$

Например, если $n=7$, $j=6$, $i=3$, то $a_6=111111$, $a_3=111$. $a_6 \equiv 5 \pmod 7$, $a_3 \equiv 6 \pmod 7$. Это плохой пример. Возьмем $n=3$. $a_1=1 \equiv 1 \pmod 3$, $a_2=11 \equiv 2 \pmod 3$, $a_3=111 \equiv 0 \pmod 3$. Это случай 1. Возьмем $n=4$. $a_1=1 \equiv 1 \pmod 4$, $a_2=11 \equiv 3 \pmod 4$, $a_3=111 \equiv 3 \pmod 4$. Здесь $i=2, j=3$. $M = a_3 - a_2 = 111-11 = 100$. Число 100 делится на 4, и в его записи только 1 и 0.

Число $M$ является натуральным, так как $j>i$. В его десятичной записи используются только цифры 1 и 0. Поскольку $M$ делится на $n$, оно является искомым числом.

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

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