Делимость чисел. Теория сравнений. Малая теорема Ферма. Примеры

Если целые числа а и b при делении на натуральное число m дают равные остатки, то говорят, что эти числа сравнимы по модулю m, и пишут a ≡ b (mod m).

(знак ≡ читают: сравнимо)

Пример.

25 = 11 ∙ 2 + 3 (число 25 при делении на 11 даёт 3 в остатке).

69 = 11 ∙ 6 + 3 (число 69 при делении на 11 даёт 3 в остатке).

По определению выше числа 25 и 69 сравнимы по модулю 11, и, следовательно, справедлива запись: 25 ≡ 69 (mod 11).

У нас а = 25, b = 69, m = 11.

Запись a ≡ b (mod m) также означает, что число a-b делится на m.

Действительно, 25-69 = -44 делится на 11.

Так же верны записи: 25 ≡ 3 (mod 11) и 69 ≡ 3 (mod 11), так как число 3 при делении на 11 тоже даёт в остатке 3. Число 25 сравнимо с числом 3 по модулю 11. Число 69 сравнимо с числом 3 по модулю 11.

Числа 25-3 и 69-3 также делятся на 11 без остатка.

Поэтому запись a ≡ b (mod m) при b < m чаще трактуют так:

b – остаток при делении а на m.

25 ≡ 3 (mod 11) – остаток при делении 25 на 11 равен 3.

69 ≡ 3 (mod 11) – остаток при делении 69 на 11 равен 3.

Запись a ≡ 0 (mod m) означает, что число а делится на m без остатка.

Свойства сравнений.

Сравнения по одному модулю можно складывать, вычитать, перемножать и возводить в степень n (натуральное), как и верные числовые равенства. Покажем это на рассмотренных сравнениях

25 ≡ 3 (mod 11) и 69 ≡ 3 (mod 11).

Складываем. 25 + 69 ≡ 3 + 3 (mod 11) → 94 ≡ 6 (mod 11). При делении 94 на 11 в остатке получаем 6.

Вычитаем. 25-69 ≡ 3-3 (mod 11) → -44 ≡ 0 (mod 11). При делении -44 на 11 в остатке получаем 0, т.е. число -44 делится на 11 без остатка.

Перемножаем. 25 ∙ 69 ≡ 3 ∙ 3 (mod 11) → 1725 ≡ 9 (mod 11). При делении 1725 на 11 в остатке получаем 9.

Возводим в степень. Имеем 25 ≡ 3 (mod 11). А нам нужен остаток от деления 25² на 11.

25 ≡ 3 (mod 11) → 25² ≡ 3² (mod 11) → 625 ≡ 9 (mod 11).

Проверьте: при делении 625 на 11 в остатке получится 9.

Ещё одно свойство сравнений.

Если ak ≡ bk (mod m), m ≠ 1, а числа k и m взаимно просты, то a ≡ b (mod m). Обе части сравнения можно сокращать на общий множитель, если он и модуль m – взаимно простые числа.

А может остаток выражаться отрицательным числом? Да. Например, при делении числа 24 на 5 в остатке получается 4.

Значит, 24 ≡ 4 (mod 5), что означает: 24 — 4 делится на 5 без остатка.

Но запись 24 ≡ -1 (mod 5) так же верна, потому что 24 -(-1) = 25 также делится на 5 без остатка.

Записи 24 ≡ 4 (mod 5) и 24 ≡ -1 (mod 5) эквивалентны.

Ещё пример: 20 ≡ 6 (mod 7) и 20 ≡ -1 (mod 7) равнозначны,

так как 20-6 = 14 делится на 7, и 20-(-1) = 21 делится на 7 без остатка.

Малая теорема Фермá.

Если m — простое число, m и а – взаимно просты, то a^m-1–1 делится на m.

Следствие. Для простого m и любого натурального а число a^m — a делится без остатка на m.

Так как из утверждения a^m-1–1 делится на m следует, что a^m-1 ≡ 1 (mod m), то именно последнее утверждение удобно применять при нахождении остатков от деления степени числа а на простое число m при условии, что числа а и m взаимно просты. Понимаем так: число a^m-1 даёт в остатке 1 при делении на m.

Примеры.

Найти остаток от деления на 11 числа 2²⁰⁰² + 3²⁰⁰².

Решение.

Используем сравнение a^m-1 ≡ 1 (mod m). У нас m = 11, значит, m-1 = 10.

Выделим из степеней 2²⁰⁰² и 3²⁰⁰² степени 2¹⁰ и 3¹⁰.

2²⁰⁰² = 2² ∙ 2²⁰⁰⁰ = 4 ∙ (2¹⁰)²⁰⁰.

3²⁰⁰² = 3² ∙ 3²⁰⁰⁰ = 9 ∙ (3¹⁰)²⁰⁰.

2²⁰⁰² + 3²⁰⁰² = 4 ∙ (2¹⁰)²⁰⁰ + 9 ∙ (3¹⁰)²⁰⁰ ≡ 4 ∙ 1²⁰⁰ (mod 11) + 9 ∙ 1²⁰⁰ (mod 11) ≡ 4 + 9 (mod 11) ≡ 2 (mod 11). Искомый остаток равен 2.

Ответ: остаток от деления на 11 числа 2²⁰⁰² + 3²⁰⁰² равен 2.

Хотите подробнее?

Мы применили утверждение a^m-1 ≡ 1 (mod m).

На самом деле: 2¹⁰ = 2^11-1 ≡ 1 (mod 11)  и  3¹⁰ = 3^11-1 ≡ 1 (mod 11), что на основании теоремы Фермá означает: числа 2¹⁰ и 3¹⁰ при делении на 11 дают в остатке 1.

Использовали свойство возведения в степень сравнений:

(2¹⁰)²⁰⁰ ≡ 1²⁰⁰ (mod 11) ≡ 1 (mod 11), а затем свойство умножения и сложения сравнений:

4 ∙ 1 (mod 11) + 9 ∙ 1 (mod 11) ≡ 4 + 9 (mod 11)  ≡ 13 (mod 11) ≡ 2 (mod 11), так как число 13 при делении на 11 даёт 2 в остатке.

А если нужно найти остаток от деления на 7 этого же числа?

Найти остаток от деления на 7 числа 2²⁰⁰² + 3²⁰⁰².

Решение. Рассуждаем точно так же.

Используем сравнение a^m-1 ≡ 1 (mod m). У нас m = 7, значит, m-1 = 6.

Выделим из степеней 2²⁰⁰² и 3²⁰⁰² степени 2⁶ и 3⁶.

2²⁰⁰² = 2⁴∙ 2¹⁹⁹⁸ = 16 ∙ (2⁶)³³³.

3²⁰⁰² = 3⁴ ∙ 3¹⁹⁹⁸ = 81 ∙ (3⁶)³³³.

2²⁰⁰² + 3²⁰⁰² = 16 ∙ (2⁶)³³³ + 81 ∙ (3⁶)³³³.

16 ≡ 2 (mod 7);

2⁶ = 2^7-1 ≡ 1 (mod 7)  →  (2⁶)³³³ ≡ 1³³³ (mod 7) ≡ 1 (mod 7);

81 ≡ 4 (mod 7);

3⁶ = 3^7-1 ≡ 1 (mod 7)  →  (3⁶)³³³ ≡ 1³³³ (mod 7) ≡ 1 (mod 7). Тогда получим:

2²⁰⁰² + 3²⁰⁰² = 16 ∙ (2⁶)³³³ + 81 ∙ (3⁶)³³³ ≡ 2 ∙ 1 + 4 ∙ 1 (mod 7) ≡ 6 (mod 7).

Ответ: остаток от деления на 7 числа 2²⁰⁰² + 3²⁰⁰² равен 6.

Найти остаток от деления на 11 числа 3²⁰⁰² + 7²⁰⁰² .

Решение.

На основании малой теоремы Фермá используем сравнение a^m-1 ≡ 1 (mod m).

У нас m = 11, значит, m-1 = 10.

Выделим из степеней 3²⁰⁰² и 7²⁰⁰² степени 2¹⁰ и 3¹⁰.

3²⁰⁰² = 3² ∙ 3²⁰⁰⁰ = 9 ∙ (3¹⁰)²⁰⁰.

7²⁰⁰² = 7² ∙ 2²⁰⁰⁰ = 49 ∙ (2¹⁰)²⁰⁰.

3²⁰⁰² + 7²⁰⁰² = 9 ∙ (2¹⁰)²⁰⁰ + 49 ∙ (3¹⁰)²⁰⁰ ≡ 9 ∙ 1²⁰⁰ + 49 ∙ 1²⁰⁰ (mod 11).

49 ≡ 5 (mod 11) т.к. при делении числа 49 на 11 в остатке будет 5. Получаем:

9 ∙ 1 + 5 ∙ 1 (mod 11) ≡ 14 (mod 11) ≡ 3 (mod 11) Искомый остаток равен 3.

Ответ: остаток от деления на 11 числа 3²⁰⁰² + 7²⁰⁰² равен 3.

Найти остаток от деления на 17 числа 2³⁶⁷ + 43.

Решение.

На основании малой теоремы Фермá ( а = 2, m = 17 – простое число, числа a и m – взаимно просты) используем сравнение a^m-1 ≡ 1 (mod m).

Так как m = 17, то m-1 = 16.

Выделим из степени 2³⁶⁷ степень 2¹⁶.

2³⁶⁷ = 2¹⁵ ∙ (2¹⁶)²² = 2¹⁰ ∙ 2⁵ ∙ (2¹⁶)²² = 1024 ∙ 32 ∙ (2^17-1)²².

1024 ≡ 4 (mod 17) – при делении 1024 на 17 получаем в остатке 4;

32 ≡ 15 (mod 17) – при делении 32 на 17 получаем в остатке 15;

2^17-1 ≡ 1 (mod 17).

Итак, 2³⁶⁷ = 1024 ∙ 32 ∙ (2^17-1)²² ≡ 4 ∙ 15 ∙ 1 (mod 17) ≡ 60 (mod 17) ≡ 9 (mod 17).

Тогда 2³⁶⁷ + 43 ≡ 9 + 43 (mod 17) ≡ 52 (mod 17) ≡ 1 (mod 17).

Ответ: остаток от деления на 17 числа 2³⁶⁷ + 43 равен 1.

Замечание. Мы могли бы вместо 32 ≡ 15 (mod 17) записать 32 ≡ -2 (mod 17).

И тогда 2³⁶⁷ = 1024 ∙ 32 ∙ (2^17-1)²² ≡ 4 ∙ (-2) ∙ 1 (mod 17) ≡ -8 (mod 17).

Отсюда 2³⁶⁷ + 43 ≡ -8 + 43 (mod 17) ≡ 35 (mod 17) ≡ 1 (mod 17).

 Найти остаток от деления на 11 числа 3²⁰²³.

Решение.

На основании малой теоремы Фермá имеем a^m-1 ≡ 1 (mod m).

Здесь а = 3, m = 11. Будет верным сравнение 3^11-1 ≡ 1 (mod 11).

3²⁰²³ = 3³ ∙ 3²⁰²⁰ = 27 ∙ (3¹⁰)²⁰².

27 ≡ 5 (mod 11) – число 27 при делении на 11 даёт в остатке 5.

(3¹⁰)²⁰² = (3^11-1)²⁰² ≡ 1²⁰² (mod 11) ≡ 1 (mod 11).

Тогда 27 ∙ (3¹⁰)²⁰² ≡ 5 ∙ 1 (mod 11) ≡ 5 (mod 11).

Ответ: остаток от деления на 11 числа 3²⁰²³ равен 5.

 Найти остаток от деления на 11 числа 2021²⁰²³.

Решение.

2021 ≡ 8 (mod 11), что означает: число 2021 сравнимо с числом 8 по модулю 11, так как при делении числа 2021 на число 11 в остатке получается 8.

2021²⁰²³ ≡ 8²⁰²³ (mod 11).

На основании малой теоремы Фермá имеем a^m-1 ≡ 1 (mod m).

Здесь а = 8, m = 11. Будет верным сравнение 8^11-1 ≡ 1 (mod 11).

8²⁰²³ = 8³ ∙ 8²⁰²⁰ = 512 ∙ (8¹⁰)²⁰².

512 ≡ 6 (mod 11) и (8¹⁰)²⁰² = (8^11-1)²⁰² ≡ 1²⁰² (mod 11) ≡ 1 (mod 11).

Тогда 512 ∙ (8¹⁰)²⁰² ≡ 6 ∙ 1 (mod 11) ≡ 6 (mod 11).

Ответ: остаток от деления на 11 числа 2021²⁰²³ равен 6.

Найти остаток от деления на 9 числа 23²⁷⁷.

Решение. число m = 9 (наш делитель) является составным, и теорема Ферма не применима.

Немного теории.

Если число А при делении на число m даёт в остатке d, то

Aⁿ (mod m) ≡ dⁿ ( mod m).

У нас 23 при делении на 9 даёт в остатке 5, поэтому

23²⁷⁷ (mod 9 ) ≡ 5²⁷⁷ (mod 9).

5²⁷⁷ (mod 9) ≡ 5 ∙ (5³)⁹² (mod 9) ≡ 5 ∙ 125⁹² (mod 9) ≡ 5 ∙ 8⁹² (mod 9) ≡

≡ 5 ∙ 64⁴⁶ (mod 9) ≡ 5 ∙ 1⁴⁶ (mod 9) ≡ 5 (mod 9).

Ответ: остаток от деления на 9 числа 23²⁷⁷ равен 5.

Найти остаток от деления на 9 числа 10²⁰²¹ + 5.

Решение.

10²⁰²¹ ≡ 1²⁰²¹ (mod 9) ≡ 1 (mod 9). Ну на самом деле, ведь остаток от деления числа 10 на число 9 равен 1. И тогда:

10²⁰²¹ + 5 ≡ 1 + 5 (mod 9) ≡ 6 (mod 9).

Ответ: остаток от деления на 9 числа 10²⁰²¹ + 5 равен 6.

Найти остаток от деления на 5 числа 39⁴⁶.

Решение.

Так как 39 = 5 ∙ 7 + 4, то 39 ≡ 4 (mod 5), следовательно, и

39⁴⁶ ≡ 4⁴⁶ (mod 5).

4⁴⁶ = 4^{2 ∙ 23} = (4²)²³ = 16²³.

16²³ ≡ 1²³ (mod 5) ≡ 1 (mod 5). При делении числа 16 на число 5 в остатке получается 1.

Ответ: остаток от деления на 5 числа 39⁴⁶ равен 1.

Найти остаток от деления на 7 числа 64²⁹.

Решение.

Так как 64 = 7 ∙ 9 +1, то 64 ≡ 1 (mod 7), следовательно, и

64²⁹ ≡ 1²⁹ (mod 7) ≡ 1 (mod 7).

Ответ: остаток от деления на 7 числа 64²⁹ равен 1.

Найти остаток от деления числа 36²⁴ + 21⁴⁵ + 7⁸ на 10.

Решение.

Так как 36 ≡ 6 (mod 10), 21 ≡ 1 (mod 10), то данное число сравнимо с числом

6²⁴ + 1⁴⁵ + 7⁸, и здесь нам не поможет малая теорема Фермá, так как не выполняются её основные условия: делитель должен быть простым числом, а основание степени и делитель взаимно просты. У нас же делитель m = 10, а это число составное.

Искомый остаток равен сумме остатков каждого из чисел 6²⁴, 1⁴⁵ и 7⁸.

Любая степень числа 6 оканчивается цифрой 6, и при делении на 10 остаток будет равен 6.

Любая определённая степень числа 1 равна 1.

Подробнее рассмотрим степень числа 7.

7¹ = 7; 7² = 49; 7³ = 343; 7⁴ = 2401; 7⁵ = 16807.

Мы поняли, что последние цифры таких чисел повторяются через 4.

Поэтому последняя цифра числа 7^k, где k Є N, определяется только тем, каков остаток от деления числа k на 4. У нас 7⁸ и k = 8, это число кратно 4, поэтому, последняя цифра числа 7⁸ равна 1, как у числа 7⁴.

Собираем остатки.

6²⁴ + 1⁴⁵ + 7⁸ ≡ 6 + 1 + 1 (mod 10) ≡ 8 (mod 10).

Ответ: остаток от деления числа 36²⁴ + 21⁴⁵ + 7⁸ на 10 равен 8.

Найти последнюю цифру числа 23²⁷⁵.

Решение. Задачу можно сформулировать иначе:

найти остаток от деления числа 23²⁷⁵ на 10.

Задача похожа на предыдущую.

23 ≡ 3 (mod 10). Это означает, что данное число будет иметь тот же остаток от деления на 10, что и число 3²⁷⁵.

Рассмотрим степени числа 3.

3¹ = 3; 3² = 9; 3³ = 27; 3⁴ = 81; 3⁵ = 243, …

Последние цифры этих степеней повторяются через 4.

Поэтому последняя цифра числа 3^k, где k Є N, определяется только тем, каков остаток от деления числа k на 4. У нас k = 275. Делим 275 на 4 и получаем в остатке 3. Значит, число 3²⁷⁵ оканчивается той же цифрой, что и число 3³, т.е. цифрой 7.

Итак, 23²⁷⁵ ≡ 3²⁷⁵ (mod 10) ≡ 7 (mod 10).

Ответ: последняя цифра числа 23²⁷⁵ равна 7 или остаток от деления числа 23²⁷⁵ на число 10 равен 7.

Остаток от деления числа а на число 3 равен 1, а от деления на 7 равен 5. Чему равен остаток от деления числа а на 21?

Решение.

Запишем условие задачи на основании теории сравнений.

Известно: a ≡ 1 (mod 3) и a ≡ 5 (mod 7). Требуется найти х, если a ≡ x (mod 21).

Мы знаем, что если число делится на 21, то оно делится и на 3 и на 7, а это означает, что a ≡ x (mod 3), а также, что a ≡ x (mod 7).

Следовательно, х ≡ 1 (mod 3) и х ≡ 5 (mod 7).

Получается, что и число х при делении на 3 даёт в остатке 1, а при делении на 7 даёт в остатке 5. И это число меньше 21. Его несложно подобрать: х = 19.

На самом деле, 19 : 3 = 6 (ост 1); 19 : 7 = 2 (ост 5) или

19 ≡ 1 (mod 3) и 19 ≡ 5 (mod 7). Итак, a ≡ 19 (mod 21).

Ответ: 19.

Найти остаток от деления числа 59 ∙ 60 ∙ 61-62 на 7.

Решение. Воспользуемся свойствами умножения и сложения сравнений.

59 ∙ 60 ∙ 61–62 ≡ 59 (mod 7) ∙ 60 (mod 7) ∙ 61 (mod 7)–62 (mod 7) ≡

≡ 3 ∙ 4 ∙ 5–6 (mod 7) ≡ 54 (mod 7) ≡ 5 (mod 7).

Ответ: 5.

Найти остаток от деления на 7 числа 65⁴³ + 54³².

Решение.

Так как 65 ≡ 2 (mod 7) и 54 ≡ 5 (mod 7), то задача сводится к нахождению остатка от деления числа 2⁴³ + 5³² на число 7.

На основании малой теоремы Фермá используем сравнение a^m-1 ≡ 1 (mod m). У нас m = 7, значит, m-1 = 6.

Выделим из степеней 2⁴³ и 5³² степени 2⁶ и 5⁶.

2⁴³ = 2∙ 2⁴² = 2 ∙ (2⁶)⁷.

5³² = 5² ∙ 5³⁰ = 25 ∙ (5⁶)⁵.

2⁴³ + 5³² = 2 ∙ (2⁶)⁷ + 25 ∙ (5⁶)⁵.

25 ≡ 4 (mod 7);

2⁶ = 2^7-1 ≡ 1 (mod 7)  →  (2⁶)⁷ ≡ 1⁷ (mod 7) ≡ 1 (mod 7);

5⁶ = 5^7-1 ≡ 1 (mod 7)  →  (5⁶)⁵ ≡ 1⁵ (mod 7) ≡ 1 (mod 7). Тогда получим:

2 ∙ (2⁶)⁷ + 25 ∙ (5⁶)⁵  ≡ 2 ∙ 1 + 4 ∙ 1 (mod 7) ≡ 6 (mod 7).

Ответ: остаток от деления на 7 числа 65⁴³ + 54³² равен 6.

Найти остаток от деления на 11 числа 2²⁹.

Решение.

На основании малой теоремы Фермá имеем a^m-1 ≡ 1 (mod m).

Здесь а = 2, m = 11. Будет верным сравнение 2^11-1 ≡ 1 (mod 11).

2²⁹ = 2⁹ ∙ 2²⁰ = 512 ∙ (2¹⁰)².

512 ≡ 6 (mod 11) – число 512 при делении на 11 даёт в остатке 6.

(2¹⁰)² = (2^11-1)² ≡ 1² (mod 11) ≡ 1 (mod 11).

Тогда 512 ∙ (2¹⁰)² ≡ 6 ∙ 1 (mod 11) ≡ 6 (mod 11).

Ответ: остаток от деления на 11 числа 2²⁹ равен 6.

Найти остаток от деления числа 32¹⁷ + 35²² на 10.

Решение.

Так как 32 ≡ 2 (mod 10), 35 ≡ 5 (mod 10), то данное число сравнимо с числом

2¹⁷ + 5²², и здесь нам не поможет малая теорема Фермá, так как не выполняются её основные условия: делитель должен быть простым числом, а основание степени и делитель взаимно просты. У нас же делитель m = 10, а это число составное.

Искомый остаток равен сумме остатков каждого из чисел 2¹⁷ и 5²².

Любая степень числа 5 оканчивается цифрой 5, и при делении на 10 остаток будет равен 5.

Подробнее рассмотрим степень числа 2.

2¹ = 2; 2² = 4; 2³ = 8; 2⁴ = 16; 2⁵ = 32.

Мы поняли, что последние цифры таких чисел повторяются через 4.

Поэтому последняя цифра числа 2^k, где k Є N, определяется только тем, каков остаток от деления числа k на 4. У нас 2¹⁷ = 2^4∙4+1, следовательно, последняя цифра числа 2¹⁷ равна 2, как у числа 2¹. Итак:

2¹⁷ + 5²² ≡ 2 + 5 (mod 10) ≡ 7 (mod 10).

Ответ: остаток от деления числа 32¹⁷ + 35²² на 10 равен 7.

Найти остаток от деления числа 2013 ∙ 2014 + 2015² на число 7.

Решение.

Используем свойства сравнений.

Найдём остатки от деления чисел 2013, 2014 и 2015 на 7.

2013 ≡ 4 (mod 7); 2014 ≡ 5 (mod 7); 2015 ≡ 6 (mod 7).

2013 ∙ 2014 + 2015² ≡ 4 ∙ 5 + 6² (mod 7) ≡ 56 (mod 7) ≡ 0 (mod 7).

Это означает, что данное число делится нацело на 7.

Ответ: остаток от деления числа 2013 ∙ 2014 + 2015² на число 7 равен 0.

Найти остаток от деления числа 20¹⁶ + 201⁶ на 9.

Решение.

По теории сравнений 20 ≡ 2 (mod 9) и 201 ≡ 3 (mod 9).

На основании свойств сравнений:

20¹⁶ + 201⁶ ≡ 2¹⁶ + 3⁶ (mod 9), и нам нужно найти остаток от деления числа

2¹⁶ + 3⁶ на 9. Заметим, что число 3⁶ делится на 9 нацело, и остаток равен 0.

Найдём остаток от деления на 9 числа 2¹⁶. Это и будет ответом к данной задаче.

2¹⁶ = (2⁶)² ∙ 2⁴ = 64² ∙ 16 ≡ 1² ∙ 7 (mod 9) ≡ 7 (mod 9).

Ответ: остаток от деления числа 20¹⁶ + 201⁶ на 9 равен 7.

Хотите порешать такие примеры самостоятельно? Отлично! Лучше решать их в виде теста онлайн — вы сразу будете видеть свои результаты и отзывы к вашим решениям. Тест «Делимость чисел» многовариантный, так что пока решаете 2-3 варианта — научитесь!