Основы теории чисел
Теория чисел изучает свойства целых чисел и правила работы с ними. В этой теме нужны четыре опоры: делимость, простые числа, разложение на простые множители и арифметика по модулю. Они помогают быстро решать задачи на НОД, НОК, остатки и перебор делителей.
Делимость и делители
Целое число \(a\) делится на ненулевое целое число \(b\), если существует целое \(k\), такое что \(a=bk\). Записывают \(b\mid a\) и читают: «\(b\) делит \(a\)». При этом \(b\) называют делителем числа \(a\), а \(a\) — кратным числа \(b\).
\(b\mid a\) тогда и только тогда, когда \(a=bk\) для некоторого целого \(k\). Если \(a=bq+r\), где \(0\le r<b\), то \(q\) — частное, а \(r\) — остаток от деления \(a\) на \(b\).
Полезны свойства делимости: если \(a\mid b\) и \(b\mid c\), то \(a\mid c\); если \(a\mid b\) и \(a\mid c\), то \(a\mid (b+c)\) и \(a\mid (b-c)\). Если \(a\mid b\), то \(a\mid kb\) для любого целого \(k\).
На \(2\) число делится, если последняя цифра чётная; на \(5\) — если последняя цифра \(0\) или \(5\); на \(3\) и \(9\) — если сумма цифр делится соответственно на \(3\) или \(9\); на \(4\) — если последние две цифры образуют число, делящееся на \(4\); на \(8\) — если последние три цифры делятся на \(8\); на \(11\) — если разность сумм цифр на нечётных и чётных местах кратна \(11\).
Простые числа и разложение
Простое число — натуральное число, большее \(1\), имеющее ровно два натуральных делителя: \(1\) и само себя. Число \(1\) простым не является. Число, большее \(1\) и не являющееся простым, называется составным.
Чтобы проверить, простое ли число \(n\), достаточно проверить делители, не превосходящие \(\sqrt n\). Если \(n\) составное, то его можно представить как \(n=ab\), где один из множителей не больше \(\sqrt n\).
Каждое натуральное число, большее \(1\), единственным образом представляется в виде произведения простых чисел с точностью до порядка множителей. Это основная теорема арифметики.
Факторизация — последовательное разложение числа на простые множители. Например, \(360=2^3\cdot3^2\cdot5\). Из разложения удобно получать количество делителей, НОД и НОК.
Если \(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s}\), то количество натуральных делителей числа \(n\) равно \((\alpha_1+1)(\alpha_2+1)\cdots(\alpha_s+1)\).
Действительно, в делителе можно выбрать степень простого \(p_i\) от \(0\) до \(\alpha_i\). Все выборы независимы, поэтому количества перемножаются.
Сколько натуральных делителей имеет число \(72=2^3\cdot3^2\)?
НОД, НОК и степени простых
Наибольший общий делитель двух чисел — наибольшее натуральное число, делящее каждое из них. Наименьшее общее кратное — наименьшее положительное число, кратное каждому из данных чисел.
Если числа разложены на простые множители, в НОД берут общие простые в меньших степенях, а в НОК — все простые в больших степенях.
Здесь \(v_p(n)\) — степень вхождения простого числа \(p\) в разложение \(n\): наибольшее \(k\), для которого \(p^k\mid n\). Например, \(v_2(40)=3\), потому что \(40=2^3\cdot5\), а \(v_3(40)=0\).
Для натуральных \(a\) и \(b\) выполняется \(\gcd(a,b)\cdot\operatorname{lcm}(a,b)=a\cdot b\).
Арифметика по модулю
Запись \(a\equiv b\pmod m\) означает, что числа \(a\) и \(b\) дают одинаковый остаток при делении на \(m\). Равносильно: \(m\mid(a-b)\). Поэтому можно заменять число на любой сравнимый с ним остаток.
Сравнения можно складывать, вычитать и перемножать: если \(a\equiv b\pmod m\) и \(c\equiv d\pmod m\), то \(a+c\equiv b+d\pmod m\) и \(ac\equiv bd\pmod m\). Возведение в натуральную степень также сохраняет сравнение.
Сначала замените основание его остатком по модулю, затем используйте цикличность степеней или быстрое возведение в квадрат. Например, при вычислении \(7^{100}\pmod {10}\) достаточно заметить цикл последних цифр: \(7,9,3,1\).
Если одновременно заданы остатки по взаимно простым модулям, например \(x\equiv a\pmod m\) и \(x\equiv b\pmod n\), можно применить китайскую теорему об остатках. Она гарантирует единственный остаток по модулю \(mn\), если \(\gcd(m,n)=1\).
Разобранный пример: делители и НОД
Найдём количество общих делителей чисел \(756\) и \(630\), а затем их сумму.
У чисел \(756\) и \(630\) ровно \(12\) общих натуральных делителей. Их сумма равна \(312\).
Не считайте число \(1\) простым. Не забывайте условие \(0\le r<m\) для остатка. В формуле количества делителей показатели степеней увеличиваются на \(1\) и затем перемножаются. Для НОД берутся минимальные показатели, для НОК — максимальные. При делении сравнения по модулю нельзя сокращать множитель без проверки: из \(ac\equiv bc\pmod m\) следует \(a\equiv b\pmod m\) только при дополнительных условиях, например \(\gcd(c,m)=1\).
Алгоритмы для задач
- Для проверки простоты перебирайте делители от \(2\) до \(\lfloor\sqrt n\rfloor\).
- Для факторизации начинайте с малых простых \(2,3,5,7\) и делите, пока деление возможно.
- Для НОД больших чисел используйте алгоритм Евклида: заменяйте пару \((a,b)\) на \((b,a\bmod b)\), пока остаток не станет нулём.
- В задачах на остатки сокращайте числа по модулю на каждом шаге.
1def gcd(a, b): 2 while b != 0: 3 a, b = b, a % b 4 return a
Проверь себя
Главное
- Делимость означает представление \(a=bk\), а остаток удовлетворяет \(a=bq+r\) и \(0\le r<b\).
- Простое разложение единственно; количество делителей находят по формуле \((\alpha_1+1)\cdots(\alpha_s+1)\).
- В НОД выбирают минимальные показатели простых, в НОК — максимальные.
- Сравнение по модулю позволяет заменять большие числа их остатками и выполнять вычисления по правилам сложения и умножения.
- Для алгоритмических задач особенно важны проверка до \(\sqrt n\), факторизация и алгоритм Евклида.