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

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

Условие.

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

Решение.

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

Рассмотрим последовательность, состоящую из 1001 натуральной степени числа 2: $2^1, 2^2, 2^3, \dots, 2^{1001}$.

Теперь найдём остатки от деления каждого из этих чисел на 1001.

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

Однако остаток от деления степени числа 2, то есть $2^k$ (где $k$ – натуральное число), на 1001 не может быть равен нулю. Это следует из того, что число 1001 не имеет в своем разложении на простые множители двойку, так как $1001 = 7 \times 11 \times 13$. В то же время, разложение числа $2^k$ на простые множители состоит только из двоек. Поскольку у чисел $2^k$ и 1001 нет общих простых делителей, $2^k$ не может делиться на 1001 нацело.

Таким образом, остатки от деления наших 1001 чисел на 1001 могут принимать только 1000 различных значений: $1, 2, 3, \dots, 1000$.

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

Это означает, что среди чисел $2^1, 2^2, \dots, 2^{1001}$ найдутся по крайней мере два различных числа, которые имеют одинаковый остаток при делении на 1001. Обозначим эти числа как $2^n$ и $2^m$, где $n$ и $m$ – различные натуральные числа из множества $\{1, 2, \dots, 1001\}$. Для определённости положим, что $n > m$.

Тот факт, что $2^n$ и $2^m$ имеют одинаковые остатки при делении на 1001, можно записать в виде сравнения по модулю:

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

Вычитая $2^m$ из обеих частей этого сравнения, получаем:

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

Это по определению означает, что разность $2^n - 2^m$ кратна числу 1001. Утверждение доказано.

Ответ: Доказательство строится на применении принципа Дирихле. Рассматривается 1001 натуральная степень числа 2. При делении этих чисел на 1001 возможны только 1000 различных ненулевых остатков. Так как степеней больше, чем возможных остатков, по крайней мере две из них будут иметь одинаковый остаток. Разность этих двух степеней будет делиться на 1001.