Профиль-математика Задачи по математике решайте как мы, решайте вместе с нами, решайте лучше нас! НАШЕ МЕНЮ НИЖЕ ВАМ В ПОМОЩЬ.
RSS
Записи с меткой "малая теорема Ферма"

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

Если целые числа а и 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 и любого натурального а число ama делится без остатка на 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)≡ 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 варианта — научитесь!

вход на сайт тестов онлайн по математике для 10 класса
Тесты по математике

Подготовка к ОГЭ по математике

Наверх