3²⁰²⁶ mod 100 без всех 967 цифр: когда работает сокращение показателя степени (Ферма и Эйлер)

145 подписчиков

12+
12+

день назад

ПожаловатьсяНарушение авторских прав

145 подписчиков

12+
12+

день назад

ПожаловатьсяНарушение авторских прав
12+
12+

день назад

Последние две цифры числа 3²⁰²⁶ — 29, это число получается без вычисления его 967 цифр. Шаг, позволяющий это сделать, — это сначала уменьшить показатель степени, и это допустимо только при определенных условиях. В этом видео показано, когда уменьшение показателя степени допустимо, почему малая теорема Ферма и теорема Эйлера позволяют это сделать, и что делать, когда их условия не выполняются. Двоичное возведение в степень уменьшает количество умножений. Теоремы Ферма и Эйлера уменьшают сам показатель степени. Разделы: 0:00 Последние две цифры числа 3²⁰²⁶ 0:34 Без каких-либо условий: возведение в квадрат, сокращение, умножение 1:16 Малая теорема Ферма и почему она верна 2:37 Таким образом, показатель степени существует по модулю p − 1, а не по модулю p 3:37 7²⁰²⁶ mod 13: сначала Ферма, затем возведение в квадрат 4:23 Составной модуль: теорема Эйлера 5:32 Подсчет φ(100) = 40 6:33 Последние две цифры числа 3²⁰²⁶, решено → 29 7:35 Меньше умножений, или меньший показатель степени Результаты: • Ферма: если p — простое число и p ∤ a, то a^(p−1) ≡ 1 (mod p). Умножение 1, 2, …, p−1 на a лишь переупорядочивает их по модулю p, а сокращение (p−1)! допустимо, поскольку НОД((p−1)!, p) = 1. • Таким образом, для простого числа p, p ∤ a и n ≥ 0 показатель степени существует по модулю p − 1: 117 = 6·18 + 9 дает 3¹¹⁷ ≡ 3⁹ ≡ 18 (mod 19). Приведение по модулю 19 вместо этого дает 3³ = 27 ≡ 8, что неверно. • 7²⁰²⁶ mod 13: 2026 = 168·12 + 10 → 7¹⁰; лестница 7, 10, 9, 3; 10 = 8 + 2 → 3·10 = 30 ≡ 4. Это требует 4 операций вместо 17. • Эйлер: если НОД(a, m) = 1, то a^φ(m) ≡ 1 (mod m), поэтому при n ≥ 0 показатель степени существует по модулю φ(m). φ(100) = 100 − 50 − 10 = 40. • Условие имеет значение: НОД(2, 100) = 2 и 2⁴⁰ ≡ 76 (mod 100), а не 1. Когда условия теоремы не выполняются, этот короткий путь нельзя применить напрямую. Бинарное возведение в степень по-прежнему работает. • Последние две цифры числа 3²⁰²⁶: 2026 = 50·40 + 26 → 3²⁶ (mod 100); лестница 3, 9, 81, 61, 21; 26 = 16 + 8 + 2 → 21·61 = 1281 ≡ 81, тогда 81·9 = 729 ≡ 29. Общий алгоритм: возведение в квадрат, сокращение и умножение для любого модуля примерно за 2·log₂ n шагов: https://www.youtube.com/watch?v=kL5rbgvlO_U Больше с канала: • Малая теорема Ферма, доказательство индукцией: https://www.youtube.com/watch?v=Ho3oqAbMBfY • Последние 2 цифры 89^122, три метода: https://www.youtube.com/watch?v=ZWEAo7JWx20 • Последние 3 цифры 2023^2023: https://www.youtube.com/watch?v=n3azIWoB3nU Больше теории чисел на https://scimigo.com #теориячисел #теоремафермата #теоремаэйлера #модулярнаяарифметика #математическоемышление

Название:

3²⁰²⁶ mod 100 без всех 967 цифр: когда работает сокращение показателя степени (Ферма и Эйлер)

Категория:

Разное