Алгоритмы теории чисел
В задачах по теории чисел нужно не столько выполнять длинные вычисления, сколько распознавать структуру числа: разложение на простые множители, общие делители, остатки и взаимную совместимость условий. Этот конспект объединяет методы, которые особенно часто встречаются в заданиях ege-25 и ege-26.
1. Разложение и делители числа
Любое натуральное число \(n>1\) однозначно представляется в виде произведения простых чисел с учётом степеней. Это основная теорема арифметики. Например, \(360=2^3\cdot3^2\cdot5\). Такое представление называют разложением на простые множители.
Если \(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\), где \(p_i\) — различные простые числа, то \(\alpha_i\) называются показателями степеней простых множителей.
Из разложения сразу находятся количество делителей и сумма делителей. Делитель выбирается независимо для каждого простого множителя: его степень может быть от \(0\) до соответствующего показателя.
Чтобы посчитать делители, не перечисляйте их. Сначала разложите число, затем примените формулу для \(\tau(n)\). Для нечётного количества делителей число должно быть полным квадратом: только у квадратного числа один из делителей — корень — не образует отдельную пару.
Если требуется проверить простоту числа \(n\), достаточно проверить простые делители, не превосходящие \(\sqrt n\). Если ни один из них не делит \(n\), число простое.
2. НОД, НОК и алгоритм Евклида
Наибольший общий делитель \(\gcd(a,b)\) — наибольшее число, делящее и \(a\), и \(b\). Наименьшее общее кратное \(\operatorname{lcm}(a,b)\) — наименьшее положительное число, кратное обоим числам.
Быстрее всего НОД находится алгоритмом Евклида. Если \(a=bq+r\), то общие делители пар \((a,b)\) и \((b,r)\) совпадают, поэтому \(\gcd(a,b)=\gcd(b,r)\).
Для целых \(a\) и \(b\) существуют такие целые \(x\) и \(y\), что \(ax+by=\gcd(a,b)\). Если \(\gcd(a,b)=1\), числа называются взаимно простыми.
Это представление важно для обратного элемента по модулю. Если \(\gcd(a,m)=1\), то из равенства \(ax+my=1\) следует \(ax\equiv1\pmod m\), то есть \(x\) — обратное к \(a\) число по модулю \(m\).
3. Сравнения и степени по модулю
Сравнение \(a\equiv b\pmod m\) означает, что \(m\) делит разность \(a-b\). Это равносильно тому, что \(a\) и \(b\) имеют одинаковый остаток при делении на \(m\). В сравнениях можно складывать, вычитать и перемножать обе части.
Возведение в степень часто упрощают по циклу остатков. Например, степени \(2\) по модулю \(7\) дают последовательность \(2,4,1\), после чего цикл длины \(3\) повторяется. Поэтому показатель можно заменить его остатком при делении на длину цикла.
Если \(p\) — простое число и \(p\nmid a\), то \(a^{p-1}\equiv1\pmod p\). Эквивалентно, \(a^p\equiv a\pmod p\) для любого целого \(a\).
Для составного модуля иногда применяют теорему Эйлера: если \(\gcd(a,m)=1\), то \(a^{\varphi(m)}\equiv1\pmod m\). Однако сначала стоит искать короткий цикл непосредственно.
Какой остаток имеет \(2^{100}\) при делении на \(7\)?
В предыдущем вопросе правильный ответ — \(2\): \(100\equiv1\pmod3\), поэтому \(2^{100}\equiv2^1\equiv2\pmod7\). Проверяйте цикл аккуратно: ошибка в остатке показателя встречается чаще самой идеи.
4. Китайская теорема об остатках
Китайская теорема об остатках помогает восстановить число по нескольким остаткам. Если модули попарно взаимно просты, система имеет единственное решение по модулю их произведения.
Для системы \(x\equiv a_i\pmod{m_i}\) при попарно взаимно простых \(m_i\) существует единственный класс решений по модулю \(M=m_1m_2\cdots m_k\).
При двух сравнениях удобно подставлять одно в другое. Пусть \(x\equiv a\pmod m\). Тогда \(x=a+mt\). Подстановка во второе сравнение превращает задачу в поиск \(t\) по одному модулю.
Найти наименьшее неотрицательное \(x\), для которого \(x\equiv2\pmod5\) и \(x\equiv3\pmod7\).
Все решения имеют вид \(x=17+35k\), потому что общий модуль равен \(5\cdot7=35\). Если модули не взаимно просты, система может не иметь решений. Например, условия \(x\equiv1\pmod4\) и \(x\equiv2\pmod6\) несовместимы: левая часть должна давать одинаковый остаток по общему делителю \(\gcd(4,6)=2\), а остатки \(1\) и \(2\) различаются по модулю 2.
5. Экзаменационный алгоритм решения
Перед вычислениями определите, что именно нужно найти: число делителей, НОД, остаток степени или число, удовлетворяющее нескольким условиям. Затем выбирайте минимальный инструмент, а не полный перебор.
- Разложите постоянные числа на простые множители, если в условии есть делимость, количество делителей или НОК.
- Сократите НОД алгоритмом Евклида; не перемножайте большие числа без необходимости.
- Для степеней найдите цикл остатков или примените теорему Ферма/Эйлера после проверки взаимной простоты.
- В системе сравнений проверьте совместимость модулей и подставьте одно выражение в другое.
- Проверьте ответ исходными условиями и укажите общий класс решений, если требуется не одно число.
Нельзя сокращать сравнение \(ac\equiv bc\pmod m\) на \(c\) без проверки: сокращение допустимо напрямую, только если \(\gcd(c,m)=1\), либо нужно заменить модуль на \(m/\gcd(c,m)\). Нельзя применять малую теорему Ферма при составном модуле без дополнительных условий. В китайской теореме нельзя автоматически перемножать модули, если они не взаимно просты. И наконец, остаток должен быть выбран в диапазоне \(0\le r<m\).
\(a\equiv b\pmod m\) означает \(m\mid(a-b)\); \(\gcd(a,b)=\gcd(b,a\bmod b)\); при взаимно простых модулях система сравнений имеет единственное решение по модулю произведения модулей.
Быстрая проверка
Проверьте себя
Главное
- Разложение на простые множители даёт формулы для числа и суммы делителей.
- НОД быстро находят алгоритмом Евклида; НОК связан с НОД формулой \(\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|\).
- В сравнениях работайте с остатками, циклами степеней и обратными элементами.
- Китайская теорема об остатках восстанавливает число по совместимым остаткам; при взаимно простых модулях общий модуль равен их произведению.
- Всегда проверяйте допустимость сокращения, условия теорем и ответ в исходных сравнениях.