Curious Maths — О математике

🔥🔵🟨 Теорема Эйлера в теории чисел + Малая теорема Ферма (пояснения, примеры и доказательства) 🎄🎁 С наступившим Новым годом, дорогие друзья! А мы с вами сегодня продолжаем исследовать математику. Сегодня поговорим про одну из самых важных теорем в теории чисел, которая используется не только для упрощения вычислений и счёта, но и очень широко применяется в современных алгоритмах криптографии (не только 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

🎃🧲 Неравенства между средними величинами (a.k.a. частный случай неравенства о средних) — Доказательство + случай равенства ➡️ Предположим, есть некоторое конечное множество A, содержащее только положительные числа a₁, a₂, ... , aₙ. Введём величины: 🔘minNum = min(a₁, a₂, ... , aₙ) 🔘HM = n / (1/a₁ + 1/a₂ + ... + 1/aₙ) (Среднее гармоническое) 🔘GM = (a₁*a₂*...*aₙ)^(1/n) (Среднее геометрическое) 🔘AM = (a₁ + a₂ + ... + aₙ) / n (Среднее арифметическое) 🔘QM = √((a₁² + a₂² + ... + aₙ²)/n) (Среднее квадратическое) 🔘maxNum = max(a₁, a₂, ... , aₙ) Тогда верна следующая цепочка неравенств: minNum ≤ HM ≤ GM ≤ AM ≤ QM ≤ maxNum (для любого n — кол-ва чисел) 📌Причём равенства наступают во всех неравенствах только одновременно и только в одном случае: a₁ = a₂ = ... = aₙ. 🌲 Существует много доказательств этой важной и полезной теоремы, сегодня мы рассмотрим способ, опирающийся на метод математической индукции. 1️⃣ — Неравенство GM ≤ AM для n = 2ᵏ: ⏩Для 2-х чисел неравенство доказать совсем нетрудно, достаточно лишь заметить и выделить полный квадрат. Почти ясно, что для любой степени двойки можно делить сумму её элементов на две и применять ранее доказанное неравенство для 2-х чисел несколько раз. Но как быть с остальными числами? 2️⃣ — Неравенство GM ≤ AM для всех чисел: ➡️ Примечательно, но здесь помогает стратегия доказывать неравенство для n-1 числа через неравенство для n чисел путём замены последней переменной на некоторый "удобный" элемент (зависящий от всех предыдущих чисел). Эту удобность можно обрести, например, потребовав от правой части принимать желаемый для нас вид: корень степени n-1 для n-1 положительного числа. 3️⃣ — Неравенство HM ≤ GM: ⏩ Непосредственно следует из GM ≤ AM после подстановки bᵢ = 1/aᵢ. 4️⃣ — Неравенство AM ≤ QM: ⏩ Не связано с предыдущими напрямую, но также доказуемо с помощью выписывания всех попарных произведений чисел из A и применения следствия из неравенства GM ≤ AM для n = 2. Главное: аккуратно посчитать количество слагаемых. 5️⃣ — minNum ≤ HM; QM ≤ maxNum: 🤗 Идейно самые понятные и простые неравенства из этой цепочки. 🌟 Важная особенность этих неравенств, которую мы ещё не затронули: все неравенства обращаются в равенства тогда и только тогда, когда все элементы из А равны между собой. В одну сторону доказывается просто (minNum = maxNum), в другую — нужно подумать, но путь очень похож на тот, который мы делали до этого. 😛 Более детально с доказательством можете ознакомиться в фотографиях поста, либо в PDF в комментариях к этому же посту! 😃 #алгебра@curious_maths

🖼 Купить NFT или попытаться выиграть его — Что лучше? (Приложение теории вероятностей) ❗️ Как многие из вас уже давно знают, в Telegram существуют NFT-подарки. Вы можете их увидеть в профилях ваших знакомых и друзей. И на самом деле, это не просто украшения — а настоящий цифровой актив. Но этот пост не об этом! 💫 На этом примере мы только рассмотрим задачу о выборе стратегии, основываясь на информации из реального источника. У нас есть 2 опции: 🩵. Купить NFT за ⭐ 900 (Телеграм-звёзд) 🩵. Попытаться выбить 7️⃣7️⃣7️⃣ в игровом автомате и забрать себе NFT, но 1 попытка стоит ⭐ 34 📊 Насчёт 1-го варианта всё понятно и прозрачно. Но сколько в среднем звёзд придётся потрать на попытки выбить комбинацию "777" в игровом автомате? Может, эта стратегия позволит сэкономить часть суммы и не отдавать ⭐️ 900? Или, может оказаться так, что нет? 🍀 Чтобы прикинуть кол-во ходов и оценить свои шансы на удачу, в этой задаче естественным образом появляется потребность в использовании математического ожидания. Мат. ожидание — это среднее, взвешенное по вероятностям значение случайной величины (в нашем случае — дискретной величины Y — количества шагов до первого выпадения "777"). Для того, чтобы найти E(Y) требуется найти вспомогательный бесконечный ряд S = Σ_{n=1}^{∞} n · (63/64)^n С помощью почленного вычитания (63/64)S из S, полученная разность этих рядов сводится к нахождению суммы бесконечно убывающей геометрической прогрессии, формулу для которой мы хорошо знаем. Оказывается, что в среднем понадобится 64 попытки для того, чтобы выбить 7️⃣7️⃣7️⃣ на игровом автомате, что влечёт за собой траты в размере ⭐️2176, что сильно больше чётких ⭐️900, за которые вы гарантированно получаете NFT. 🚨 Поэтому, несмотря на малую цену за 1 попытку, вы наверняка потратите больше своих денег, а получите (а может, и не получите!) в точности то же самое. Не стоит вестись на кажущуюся "лёгкость") #теориявероятностей@curious_maths

🌵 Друзья, наверняка многие из вас задумываются над вопросом — а чем себя можно занять летом? Вы закончили школу, или сдали сессию в ВУЗе, но чувствуете, что теперь не знаете, чем себя занять? 💃 Как вам идея порешать задачи из математического анализа? ➡️ В канале Практикум || Интегралы и ряды проводится конкурс на решение задач на очень хорошие интегралы и ряды. Это — отличный шанс подумать над сложными задачами и улучшить свои хард-скиллы в матанализе! 🤑 В конкурсе предусмотрены призовые места с денежными призами: 🌟 1️⃣ место — 10 тыс. рублей ⭐️ 2️⃣ место — 5 тыс. рублей ⭐️ 3️⃣ место — 3 тыс. рублей ⭐️ 🩵🩵🩵 место — 1 тыс. рублей 📕 Всего предлагается решить 42 задачи. Каждый день в ~12:00 публикуется новая задача, но сдавать их можно в любое время и в любом порядке. ❗️Конец — 17 августа, но присоединиться к решению задач можно в любое время. Как вам будет удобно. Подробнее про конкурс вы можете почитать здесь и здесь — а я вам желаю приятного решения задач!

⬆️ Также напоминаю про эти ещё не решённые задачи

⬆️ Также напоминаю про эти ещё не решённые задачи

▶️Задача для самостоятельного решения — уравнение с обратными тригонометрическими функциями 📌 Своими мыслями и полными решениями делитесь в комментариях к этому посту! #алгебра@curious_maths #тригонометрия@curious_maths

➡️ Друзья, создание таких постов занимает большое количество времени и сил. И дело не в том, чтобы понять и решить задачу, а в том, чтобы доходчиво объяснить её Вам — чтобы максимальное число читающих смогло понять материал. Поэтому если вам по душе подача или материалы, то я буду очень благодарен за Ваши ⭐️Звёздные реакции и ⚡ Бусты Спасибо ✊