🔥🔵🟨 Теорема Эйлера в теории чисел + Малая теорема Ферма (пояснения, примеры и доказательства) 🎄🎁 С наступившим Новым годом, дорогие друзья! А мы с вами сегодня продолжаем исследовать математику. Сегодня поговорим про одну из самых важных теорем в теории чисел, которая используется не только для упрощения вычислений и счёта, но и очень широко применяется в современных алгоритмах криптографии (не только RSA, но и p-1-метод Полларда, ECM, метод квадратичного решета и очень многие другие) ➡️ Возможно, вам когда-нибудь задавалось наблюдать за тем, как ведут себя натуральные степени некоторого натурального числа по некоторому модулю. То есть, удавалось распознать какую-то закономерность, паттерн, которому подчиняются остатки при делении этих степеней на некоторое известное число. И правда: степени рано или поздно зацикливаются! Но с чем это связано, почему соблюдается такая структура? ➡️ Всё кроется в теореме Эйлера (для теории чисел), тесно связанной с функцией Эйлера, которую мы уже рассматривали ранее. Оказывается, если рассмотреть все взаимно простые с N числа, меньшие его самого, то при умножении каждого из этих чисел на некоторое другое число A (также взаимно простое с N), рассматриваемые числа будут просто переходить друг в друга по модулю N, что никак не затрагивает их произведение. Это ключевая идея, которая используется в доказательстве. 📌 Теорема Эйлера (формулировка): Если a и m взаимно просты, то a^φ(m) ≡ 1 (mod m) С доказательством можно ознакомиться на листочке. Так или иначе, теперь мы знаем очень мощный инструмент, который способен сильно упрощать арифметику при весьма трудоёмких вычислениях. Теперь должно стать проще понять, почему нельзя(!) брать остаток от деления в показателях по известному модулю N. Чтобы "перебраться" в показатель степени, нужно: 1️⃣ Проверить, что основание степени и модуль N взаимно простые; 2️⃣ Найти остаток показателя по модулю φ(N). 🔘Можно обобщить на башни степеней: например, на числа вида a^b^c. Тогда во втором показателе придётся найти остаток по модулю φ(φ(N)). Как думаете, а сколько композиций функции Эйлера будет достаточно (сколько раз нужно будет применить φ), чтобы число N превратить в 1? Оказывается, всегда будет достаточно не более log₂N композиций (постарайтесь осознать, почему так). Теперь про малую теорему Ферма: 📌 Малая теорема Ферма (формулировка): Если a не делится на простое число p, то aᵖ⁻¹ ≡ 1 (mod p) Доказательство тривиальное, если знать теорему Эйлера: нужно лишь применить функцию Эйлера для простого числа p и отразить это в итоговой формуле. ❗️ Важно также понимать, что как теорема Эйлера, так и её следствие в виде малой теоремы Ферма, не способны всегда находить наименьшую степень числа, в которой оно сравнимо с 1 по некоторому модулю. Но степень φ(n), при соблюдении остальных условий, всегда гарантирует в результате 1 в сравнении. Например, это становится яснее в такой ситуации: 17¹⁷⁸ ≡ 1 (mod 179) — по малой теореме Ферма 17⁸⁹ ≡ 1 (mod 179) — степень вдвое меньше ⬛️А как вы думаете, если сегодня воскресенье, то какой день недели будет через 10^10^100 дней? Делитесь своими мыслями и решениями в комментариях! #алгебра@curious_maths #теориячисел@curious_maths