Делимость чисел. Теория сравнений. Малая теорема Ферма. Примеры
Если целые числа а и 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). А нам нужен остаток от деления 252 на 11.
25 ≡ 3 (mod 11) → 252 ≡ 32 (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 и а – взаимно просты, то am-1–1 делится на m.
Следствие. Для простого m и любого натурального а число am — a делится без остатка на m.
Так как из утверждения am-1–1 делится на m следует, что am-1 ≡ 1 (mod m), то именно последнее утверждение удобно применять при нахождении остатков от деления степени числа а на простое число m при условии, что числа а и m взаимно просты. Понимаем так: число am-1 даёт в остатке 1 при делении на m.
Примеры.
Найти остаток от деления на 11 числа 22002 + 32002.
Решение.
Используем сравнение am-1 ≡ 1 (mod m). У нас m = 11, значит, m-1 = 10.
Выделим из степеней 22002 и 32002 степени 210 и 310.
22002 = 22 ∙ 22000 = 4 ∙ (210)200.
32002 = 32 ∙ 32000 = 9 ∙ (310)200.
22002 + 32002 = 4 ∙ (210)200 + 9 ∙ (310)200 ≡ 4 ∙ 1200 (mod 11) + 9 ∙ 1200 (mod 11) ≡ 4 + 9 (mod 11) ≡ 2 (mod 11). Искомый остаток равен 2.
Ответ: остаток от деления на 11 числа 22002 + 32002 равен 2.
Хотите подробнее?
Мы применили утверждение am-1 ≡ 1 (mod m).
На самом деле: 210 = 211-1 ≡ 1 (mod 11) и 310 = 311-1 ≡ 1 (mod 11), что на основании теоремы Фермá означает: числа 210 и 310 при делении на 11 дают в остатке 1.
Использовали свойство возведения в степень сравнений:
(210)200 ≡ 1200 (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 числа 22002 + 32002.
Решение. Рассуждаем точно так же.
Используем сравнение am-1 ≡ 1 (mod m). У нас m = 7, значит, m-1 = 6.
Выделим из степеней 22002 и 32002 степени 26 и 36.
22002 = 24∙ 21998 = 16 ∙ (26)333.
32002 = 34 ∙ 31998 = 81 ∙ (36)333.
22002 + 32002 = 16 ∙ (26)333 + 81 ∙ (36)333.
16 ≡ 2 (mod 7);
26 = 27-1 ≡ 1 (mod 7) → (26)333 ≡ 1333 (mod 7) ≡ 1 (mod 7);
81 ≡ 4 (mod 7);
36 = 37-1 ≡ 1 (mod 7) → (36)333 ≡ 1333 (mod 7) ≡ 1 (mod 7). Тогда получим:
22002 + 32002 = 16 ∙ (26)333 + 81 ∙ (36)333 ≡ 2 ∙ 1 + 4 ∙ 1 (mod 7) ≡ 6 (mod 7).
Ответ: остаток от деления на 7 числа 22002 + 32002 равен 6.
Найти остаток от деления на 11 числа 32002 + 72002 .
Решение.
На основании малой теоремы Фермá используем сравнение am-1 ≡ 1 (mod m).
У нас m = 11, значит, m-1 = 10.
Выделим из степеней 32002 и 72002 степени 210 и 310.
32002 = 32 ∙ 32000 = 9 ∙ (310)200.
72002 = 72 ∙ 22000 = 49 ∙ (210)200.
32002 + 72002 = 9 ∙ (210)200 + 49 ∙ (310)200 ≡ 9 ∙ 1200 + 49 ∙ 1200 (mod 11).
49 ≡ 5 (mod 11) т.к. при делении числа 49 на 11 в остатке будет 5. Получаем:
9 ∙ 1 + 5 ∙ 1 (mod 11) ≡ 14 (mod 11) ≡ 3 (mod 11) Искомый остаток равен 3.
Ответ: остаток от деления на 11 числа 32002 + 72002 равен 3.
Найти остаток от деления на 17 числа 2367 + 43.
Решение.
На основании малой теоремы Фермá ( а = 2, m = 17 – простое число, числа a и m – взаимно просты) используем сравнение am-1 ≡ 1 (mod m).
Так как m = 17, то m-1 = 16.
Выделим из степени 2367 степень 216.
2367 = 215 ∙ (216)22 = 210 ∙ 25 ∙ (216)22 = 1024 ∙ 32 ∙ (217-1)22.
1024 ≡ 4 (mod 17) – при делении 1024 на 17 получаем в остатке 4;
32 ≡ 15 (mod 17) – при делении 32 на 17 получаем в остатке 15;
217-1 ≡ 1 (mod 17).
Итак, 2367 = 1024 ∙ 32 ∙ (217-1)22 ≡ 4 ∙ 15 ∙ 1 (mod 17) ≡ 60 (mod 17) ≡ 9 (mod 17).
Тогда 2367 + 43 ≡ 9 + 43 (mod 17) ≡ 52 (mod 17) ≡ 1 (mod 17).
Ответ: остаток от деления на 17 числа 2367 + 43 равен 1.
Замечание. Мы могли бы вместо 32 ≡ 15 (mod 17) записать 32 ≡ -2 (mod 17).
И тогда 2367 = 1024 ∙ 32 ∙ (217-1)22 ≡ 4 ∙ (-2) ∙ 1 (mod 17) ≡ -8 (mod 17).
Отсюда 2367 + 43 ≡ -8 + 43 (mod 17) ≡ 35 (mod 17) ≡ 1 (mod 17).
Найти остаток от деления на 11 числа 32023.
Решение.
На основании малой теоремы Фермá имеем am-1 ≡ 1 (mod m).
Здесь а = 3, m = 11. Будет верным сравнение 311-1 ≡ 1 (mod 11).
32023 = 33 ∙ 32020 = 27 ∙ (310)202.
27 ≡ 5 (mod 11) – число 27 при делении на 11 даёт в остатке 5.
(310)202 = (311-1)202 ≡ 1202 (mod 11) ≡ 1 (mod 11).
Тогда 27 ∙ (310)202 ≡ 5 ∙ 1 (mod 11) ≡ 5 (mod 11).
Ответ: остаток от деления на 11 числа 32023 равен 5.
Найти остаток от деления на 11 числа 20212023.
Решение.
2021 ≡ 8 (mod 11), что означает: число 2021 сравнимо с числом 8 по модулю 11, так как при делении числа 2021 на число 11 в остатке получается 8.
20212023 ≡ 82023 (mod 11).
На основании малой теоремы Фермá имеем am-1 ≡ 1 (mod m).
Здесь а = 8, m = 11. Будет верным сравнение 811-1 ≡ 1 (mod 11).
82023 = 83 ∙ 82020 = 512 ∙ (810)202.
512 ≡ 6 (mod 11) и (810)202 = (811-1)202 ≡ 1202 (mod 11) ≡ 1 (mod 11).
Тогда 512 ∙ (810)202 ≡ 6 ∙ 1 (mod 11) ≡ 6 (mod 11).
Ответ: остаток от деления на 11 числа 20212023 равен 6.
Найти остаток от деления на 9 числа 23277.
Решение. число m = 9 (наш делитель) является составным, и теорема Ферма не применима.
Немного теории.
Если число А при делении на число m даёт в остатке d, то
An (mod m) ≡ dn ( mod m).
У нас 23 при делении на 9 даёт в остатке 5, поэтому
23277 (mod 9 ) ≡ 5277 (mod 9).
5277 (mod 9) ≡ 5 ∙ (53)92 (mod 9) ≡ 5 ∙ 12592 (mod 9) ≡ 5 ∙ 892 (mod 9) ≡
≡ 5 ∙ 6446 (mod 9) ≡ 5 ∙ 146 (mod 9) ≡ 5 (mod 9).
Ответ: остаток от деления на 9 числа 23277 равен 5.
Найти остаток от деления на 9 числа 102021 + 5.
Решение.
102021 ≡ 12021 (mod 9) ≡ 1 (mod 9). Ну на самом деле, ведь остаток от деления числа 10 на число 9 равен 1. И тогда:
102021 + 5 ≡ 1 + 5 (mod 9) ≡ 6 (mod 9).
Ответ: остаток от деления на 9 числа 102021 + 5 равен 6.
Найти остаток от деления на 5 числа 3946.
Решение.
Так как 39 = 5 ∙ 7 + 4, то 39 ≡ 4 (mod 5), следовательно, и
3946 ≡ 446 (mod 5).
446 = 42 ∙ 23 = (42)23 = 1623.
1623 ≡ 123 (mod 5) ≡ 1 (mod 5). При делении числа 16 на число 5 в остатке получается 1.
Ответ: остаток от деления на 5 числа 3946 равен 1.
Найти остаток от деления на 7 числа 6429.
Решение.
Так как 64 = 7 ∙ 9 +1, то 64 ≡ 1 (mod 7), следовательно, и
6429 ≡ 129 (mod 7) ≡ 1 (mod 7).
Ответ: остаток от деления на 7 числа 6429 равен 1.
Найти остаток от деления числа 3624 + 2145 + 78 на 10.
Решение.
Так как 36 ≡ 6 (mod 10), 21 ≡ 1 (mod 10), то данное число сравнимо с числом
624 + 145 + 78, и здесь нам не поможет малая теорема Фермá, так как не выполняются её основные условия: делитель должен быть простым числом, а основание степени и делитель взаимно просты. У нас же делитель m = 10, а это число составное.
Искомый остаток равен сумме остатков каждого из чисел 624, 145 и 78.
Любая степень числа 6 оканчивается цифрой 6, и при делении на 10 остаток будет равен 6.
Любая определённая степень числа 1 равна 1.
Подробнее рассмотрим степень числа 7.
71 = 7; 72 = 49; 73 = 343; 74 = 2401; 75 = 16807.
Мы поняли, что последние цифры таких чисел повторяются через 4.
Поэтому последняя цифра числа 7k, где k Є N, определяется только тем, каков остаток от деления числа k на 4. У нас 78 и k = 8, это число кратно 4, поэтому, последняя цифра числа 78 равна 1, как у числа 74.
Собираем остатки.
624 + 145 + 78 ≡ 6 + 1 + 1 (mod 10) ≡ 8 (mod 10).
Ответ: остаток от деления числа 3624 + 2145 + 78 на 10 равен 8.
Найти последнюю цифру числа 23275.
Решение. Задачу можно сформулировать иначе:
найти остаток от деления числа 23275 на 10.
Задача похожа на предыдущую.
23 ≡ 3 (mod 10). Это означает, что данное число будет иметь тот же остаток от деления на 10, что и число 3275.
Рассмотрим степени числа 3.
31 = 3; 32 = 9; 33 = 27; 34 = 81; 35 = 243, …
Последние цифры этих степеней повторяются через 4.
Поэтому последняя цифра числа 3k, где k Є N, определяется только тем, каков остаток от деления числа k на 4. У нас k = 275. Делим 275 на 4 и получаем в остатке 3. Значит, число 3275 оканчивается той же цифрой, что и число 33, т.е. цифрой 7.
Итак, 23275 ≡ 3275 (mod 10) ≡ 7 (mod 10).
Ответ: последняя цифра числа 23275 равна 7 или остаток от деления числа 23275 на число 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 числа 6543 + 5432.
Решение.
Так как 65 ≡ 2 (mod 7) и 54 ≡ 5 (mod 7), то задача сводится к нахождению остатка от деления числа 243 + 532 на число 7.
На основании малой теоремы Фермá используем сравнение am-1 ≡ 1 (mod m). У нас m = 7, значит, m-1 = 6.
Выделим из степеней 243 и 532 степени 26 и 56.
243 = 2∙ 242 = 2 ∙ (26)7.
532 = 52 ∙ 530 = 25 ∙ (56)5.
243 + 532 = 2 ∙ (26)7 + 25 ∙ (56)5.
25 ≡ 4 (mod 7);
26 = 27-1 ≡ 1 (mod 7) → (26)7 ≡ 17 (mod 7) ≡ 1 (mod 7);
56 = 57-1 ≡ 1 (mod 7) → (56)5 ≡ 15 (mod 7) ≡ 1 (mod 7). Тогда получим:
2 ∙ (26)7 + 25 ∙ (56)5 ≡ 2 ∙ 1 + 4 ∙ 1 (mod 7) ≡ 6 (mod 7).
Ответ: остаток от деления на 7 числа 6543 + 5432 равен 6.
Найти остаток от деления на 11 числа 229.
Решение.
На основании малой теоремы Фермá имеем am-1 ≡ 1 (mod m).
Здесь а = 2, m = 11. Будет верным сравнение 211-1 ≡ 1 (mod 11).
229 = 29 ∙ 220 = 512 ∙ (210)2.
512 ≡ 6 (mod 11) – число 512 при делении на 11 даёт в остатке 6.
(210)2 = (211-1)2 ≡ 12 (mod 11) ≡ 1 (mod 11).
Тогда 512 ∙ (210)2 ≡ 6 ∙ 1 (mod 11) ≡ 6 (mod 11).
Ответ: остаток от деления на 11 числа 229 равен 6.
Найти остаток от деления числа 3217 + 3522 на 10.
Решение.
Так как 32 ≡ 2 (mod 10), 35 ≡ 5 (mod 10), то данное число сравнимо с числом
217 + 522, и здесь нам не поможет малая теорема Фермá, так как не выполняются её основные условия: делитель должен быть простым числом, а основание степени и делитель взаимно просты. У нас же делитель m = 10, а это число составное.
Искомый остаток равен сумме остатков каждого из чисел 217 и 522.
Любая степень числа 5 оканчивается цифрой 5, и при делении на 10 остаток будет равен 5.
Подробнее рассмотрим степень числа 2.
21 = 2; 22 = 4; 23 = 8; 24 = 16; 25 = 32.
Мы поняли, что последние цифры таких чисел повторяются через 4.
Поэтому последняя цифра числа 2k, где k Є N, определяется только тем, каков остаток от деления числа k на 4. У нас 217 = 24∙4+1, следовательно, последняя цифра числа 217 равна 2, как у числа 21. Итак:
217 + 522 ≡ 2 + 5 (mod 10) ≡ 7 (mod 10).
Ответ: остаток от деления числа 3217 + 3522 на 10 равен 7.
Найти остаток от деления числа 2013 ∙ 2014 + 20152 на число 7.
Решение.
Используем свойства сравнений.
Найдём остатки от деления чисел 2013, 2014 и 2015 на 7.
2013 ≡ 4 (mod 7); 2014 ≡ 5 (mod 7); 2015 ≡ 6 (mod 7).
2013 ∙ 2014 + 20152 ≡ 4 ∙ 5 + 62 (mod 7) ≡ 56 (mod 7) ≡ 0 (mod 7).
Это означает, что данное число делится нацело на 7.
Ответ: остаток от деления числа 2013 ∙ 2014 + 20152 на число 7 равен 0.
Найти остаток от деления числа 2016 + 2016 на 9.
Решение.
По теории сравнений 20 ≡ 2 (mod 9) и 201 ≡ 3 (mod 9).
На основании свойств сравнений:
2016 + 2016 ≡ 216 + 36 (mod 9), и нам нужно найти остаток от деления числа
216 + 36 на 9. Заметим, что число 36 делится на 9 нацело, и остаток равен 0.
Найдём остаток от деления на 9 числа 216. Это и будет ответом к данной задаче.
216 = (26)2 ∙ 24 = 642 ∙ 16 ≡ 12 ∙ 7 (mod 9) ≡ 7 (mod 9).
Ответ: остаток от деления числа 2016 + 2016 на 9 равен 7.
Хотите порешать такие примеры самостоятельно? Отлично! Лучше решать их в виде теста онлайн — вы сразу будете видеть свои результаты и отзывы к вашим решениям. Тест «Делимость чисел» многовариантный, так что пока решаете 2-3 варианта — научитесь!
Навигация
Предыдущая статья: ← 15 декабря планируется взять кредит в банке на сумму 1100 тысяч рублей на 16 месяцев
Следующая статья: На одной полке стоит 36 блюдец: 14 синих и 22 красных →
Комментирование закрыто.