Делимость

Возьмём два целых числа $a, b \in \ZZ$ . Говорят, что число $a$ делит число $b$ , если существует такое число $c \in \ZZ$ , что $b = a \cdot c$ . Записывается как $a \divides b$ .

a \divides b \defequiv \exists\, c \in \ZZ \? b = a \cdot c

Такое отношение можно ввести для любых колец, но этим мы займёмся сильно позже. Пока смотрим только на $\ZZ$ .

Об обозначении знака деления

В математической литературе используют знак $a \mid b$ вместо $a \divides b$ , когда пишут, что $a$ делит $b$ . Я буду использовать обозначение $\divides$ вместо стандартного $\mid$ .

Во-первых, нужно отличать черту-деление от черты-свойства, например, в нотации с множествами. Оцените, как бы выглядела запись со стандартным обозначением

\{ g \mid g \mid a\land g \mid b \}

Здесь целых три вертикальных черты, которые создают слишком много шума.

Во-вторых, с вертикальными чертами выходит явный перебор. Они используются в обозначениях модуля, определителя, норм, условных вероятностей и статистик, порядков групп, сужения функций, для указания свойств объектов и конкатенации строк. А с обратным слешем наоборот, явный недобор. Использется он только для указания разности множеств, но в случае со множествами, смысл знака понятен из контекста.

В-третьих, наклон черты влево создаёт естественную ассоциацию с операцией деления: запись $a \divides b$ визуально напоминает, что $b/a$ должно быть целым.

Этот выбор не является нововведением — он следует обозначениям, принятым в авторитетной работе «Конкретная математика» за авторством Рональда Грэхема, Дональда Кнута и Орена Паташника. В своей работе авторы сознательно отказались от перегруженной вертикальной черты в пользу более ясного символа, а мне эта идея очень сильно понравилась.

НОК и НОД

Набольший общей делитель

Пусть есть два числа $a, b \in \ZZ$ . Можно посмотреть на множество их общих делителей

\{ g \in \ZZ : g \divides a \land g \divides b \}

Если хотя бы одно из чисел $a$ и $b$ не равно $0$ , то в этом множестве есть максимальный элемент, который является наибольшим общим делителем чисел $a$ и $b$ .

\gcd(a, b) \defeq \max\limits~ \{ g : g \divides a \land g \divides b \}

По определению считаем, что $\gcd(0, 0) \defeq 0$ .

Аналогично общим делителям, можно рассмотреть общие кратные двух чисел $a, b \in \ZZ$ . Это такие числа $m$ , которые делятся и на $a$ , и на $b$ .

\{ m \in \ZZ : a \divides m \land b \divides m \}

Среди всех положительных общих кратных существует наименьшее. Это число называется наименьшим общим кратным чисел $a$ и $b$ и обозначается $\lcm(a, b)$ .

\lcm(a, b) \defeq \min\limits~ \{ m : a \divides m \land b \divides m \}

Из обоих определений сразу можно получить несколько полезных свойств.

Наибольший общий делитель и наименьшее общее кратное — операции симметричные и инвариантные относительно знака, то есть

\gcd(a, b) = \gcd(b, a) = \gcd(|a|, |b|)

\lcm(a, b) = \lcm(b, a) = \lcm(|a|, |b|)

Связь наибольшего общего делителя и наименьшего общего кратного

Для любых ненулевых целых $a, b$

\gcd(a, b) \cdot \lcm(a, b) = |a \cdot b|

Пусть $d = \gcd(a, b)$ . Тогда $a = d \, a'$ , $b = d \, b'$ , где $\gcd(a', b') = 1$ . Для доказательства теоремы достаточно показать, что $\lcm(a, b) = d \, a' \, b'$ . С одной стороны, $d \, a' \, b'$ кратно обоим числам. С другой, любое общее кратное $m$ должно делиться на $d \, a' \, b'$ , поскольку $a'$ и $b'$ взаимно просты.

Таким образом, $\lcm(a, b) = d \, a' \, b' = ab / d = |ab| / \gcd(a, b)$ .

Наибольший общий делитель и наименьшее общее кратное можно рассматривать не только для двух чисел, но и для любого количества чисел, ведь обе операции ассоциативные

\gcd \bigl( a, \gcd(b, c) \bigr) = \gcd \bigl( \gcd(a, b), c \bigr)

\lcm \bigl( a, \lcm(b, c) \bigr) = \lcm \bigl( \lcm(a, b), c \bigr)

Тогда можно определить наибольший общий делитель и наименьшее общее кратное нескольких чисел

\gcd (a_1, a_2, \dotsc, a_n) \defeq \max\limits~ \{ g : g \divides a_1 \land g \divides a_2 \land \dotsb \land g \divides a_n \} = \gcd(a_1, \gcd(a_2, \gcd(\cdots, \gcd(a_{n-1}, a_n) \cdots )

\lcm (a_1, a_2, \dotsc, a_n) \defeq \min\limits~ \{ m : a_1 \divides m \land a_2 \divides m \land \dotsb \land a_n \divides m \} = \lcm(a_1, \lcm(a_2, \lcm(\cdots, \lcm(a_{n-1}, a_n) \cdots )

Набольший общий делитель дистрибутивен по наименьшему общему кратному и наоборот, то есть

\lcm \bigl(a, \gcd(b, c) \bigr) = \gcd \bigl( \lcm(a, b),~ \lcm(a, c) \bigr)

\gcd \bigl(a, \lcm(b, c) \bigr) = \lcm \bigl( \gcd(a, b),~ \gcd(a, c) \bigr)

Эти тождества показывают, что НОК и НОД образуют дистрибутивную решётку на множестве натуральных чисел.

Простые числа

Простое число — целое число, у которого ровно $2$ делителя: $1$ и оно само. Число $1$ простым не считается.

Множество простых чисел иногда обозначается $P$ .

Если два числа $a$ и $b$ не имеют общий делителей, то есть если $\gcd(a, b) = 1$ , то эти два числа называются взаимнопростыми. Записывается этот факт $a \rprime b$ .

a \rprime b \defequiv \gcd(a, b) = 1

Лемма и теорема Евклида

Теорема Евклида доказывает существование бесконечного количества простых чисел, что позволяет нам пользоваться свойствами простых чисел на всем множестве целых чисел исключая 0.

Лемма Евклида

Пусть $p$ — простое число и $a, b \in \ZZ$ . Если $p \divides a \cdot b$ , то $p \divides a$ или $p \divides b$ .

Предположим, что $p \nmid a$ (КАК НАПИСАТЬ?). Поскольку $p$ — простое, из этого следует, что $\gcd(p, a) = 1$ . По теореме Безу существуют целые числа $x, y$ такие, что

p x + a y = 1.

Умножим обе части этого равенства на $b$ , напомню, что $p \divides ab$ :

p x b + a b y = b.

По условию леммы $p \divides a b$ и очевидно, что $p \divides p x b$ . Следовательно, $p$ делит левую часть, а значит, делит и правую — то есть $p \divides b$ .

Лемма Евклида лежит в основе доказательства Теоремы Евклида. Она выглядит следующим образом:

Если простое число $p$ делит произведение $a_1 a_2 \dotsm a_k$ , то $p$ делит хотя бы один из множителей $a_i$ .

Доказательство проводится индукцией. База $k = 2$ . Предположим, утверждение верно для $k - 1$ , и пусть $p \divides a_1 \dotsm a_k$ . Обозначим $A = a_1 \dotsm a_{k-1}$ , тогда $p \divides A \cdot a_k$ . По лемме Евклида, либо $p \divides A$ , либо $p \divides a_k$ . В первом случае по предположению индукции $p$ делит один из $a_1, \dotsc, a_{k-1}$ , во втором — делит $a_k$ .

Основная теорема арифметики

Любое натуральное число $n > 1$ может быть единственным образом представлено в виде произведения простых чисел:

n = \prod\limits_{k=1}^n p_k = p_1 \cdot p_2 \cdot p_3 \dotsm p_{m-1} \cdot p_m

Под единственностью разложения здесь понимается единственность с точностью до порядка множителей.

Другой, иногда более удобный способ представления чисел

n = \prod\limits_{p ~\text{простое}} p^{n_p} \quad\text{где каждое}~ n_p \ge 0

Предположим, что существует натуральное число, имеющее два различных разложения на простые множители. Пусть $n > 1$ — наименьшее такое число. Тогда

n = p_1 \cdot p_2 \dotsm p_k = q_1 \cdot q_2 \dotsm q_m,

где все $p_i$ и $q_j$ — простые числа.

Рассмотрим простое число $p_1$ . Оно делит левую часть, а значит, делит и правую. По лемме Евклида, если простое число делит произведение, то оно делит хотя бы один из множителей. Следовательно, существует индекс $j$ такой, что $p_1 \divides q_j$ . Но $q_j$ — простое и не еденица, поэтому $p_1 = q_j$ . Следовательно мы можем разделить $n$ на $p_1$ .

Разделим обе части равенства на $p_1$ :

\frac{n}{p_1} = p_2 \dotsm p_k = q_2 \dotsm q_m.

Получили, что число $n / p_1 < n$ также имеет два различных разложения на простые множители. Это противоречит выбору $n$ как наименьшего контрпримера.

Следовательно, наше предположение неверно, и разложение любого натурального числа $n > 1$ на простые множители единственно.

Основная теорема арифметики позволяет нам каждое натуральное число $n$ представить «каноническом» виде $n = \langle n_2, n_3, n_5, n_7, n_{11}], \dotsc \rangle$ . Здесь $n_p$ — степень вхождения числа $p$ в разложение числа $n$ на простые множители.

Например, число $84$ представимо как

84 = \langle 2, 1, 0, 1, 0, 0, 0, \dotsc \rangle = 2^2 \cdot 3 \cdot 7

При умножении двух чисел компоненты их канонического разложения складываются:

k = n \cdot m \Leftrightarrow k_p = n_p + m_p \quad\text{при всех простых}~ p

Отсюда выводим важный факт для делимости

d \divides n \leftrightarrow d_p \le n_p \quad\text{при всех простых } p

Разложение на простые множители

Перед тем как раскаладывать число на простые делители, попробуем найти границы, в которых мы будем искать наши делители. Логично, что искомые простые делители числа $n$ соответсвуют неравенству $1 < p < n$ , но мы хотим сузить границы поиска.

Оценка наименьшего простого делителя

Пусть $n \in \NN$ , $n > 1$ . Если $n$ — составное число, то оно имеет простой делитель $p$ такой, что $p \le \sqrt{n}$ .

Поскольку $n$ составное, существуют целые числа $a, b$ такие, что $1 < a < n$ , $1 < b < n$ и $n = a \cdot b$ . Пусть $a \le b$ . Тогда истинно

a^2 \le a \cdot b = n,

откуда следует $a \le \sqrt{n}$ . Число $a$ имеет хотя бы один простой делитель $p$ (поскольку $a > 1$ ), и этот делитель также делит $n$ , так как $p \divides a$ и $a \divides n$ , то $p \divides n$ (из-за транзитивности делимости). И поскольку $p \le a$ , получаем $p \le \sqrt{n}$ .

Для практического нахождения канонического разложения применяется следующий алгоритм:

Возьмём $m = n$ , $i = 1$ . На каждом шаге ищем наименьший простой делитель $p_i$ текущего значения $m$ , определяем максимальную степень $\alpha_i$ , такую что $p_i^{\alpha_i} \divides m$ , затем приравниваем $m = m / p_i^{\alpha_i}$ . Если после этого $m = 1$ , алгоритм завершён, иначе увеличиваем индекс $i$ на единицу и повторяем процесс.

Но зная что любое составное число имеет простой делитель такой, что $p \le \sqrt{n}$ , то достаточно проверять делители начиная с $2$ не превосходящие $\sqrt{m}$ , если после исчерпания всех простых $p \le \sqrt{m}$ остаток $m > 1$ , то он сам является простым числом.

Вычисление НОД и НОК через каноническое разложение

Пусть $a, b \in \NN$ и их канонические разложения имеют вид

a = \prod\limits_{p ~\text{простое}} p^{\alpha_p}, \quad b = \prod\limits_{p ~\text{простое}} p^{\beta_p},

где $\alpha_p, \beta_p \in \NN$ . Тогда:

\gcd(a, b) = \prod\limits_{p ~\text{простое}} p^{\min\limits(\alpha_p,\, \beta_p)}, \quad \lcm(a, b) = \prod\limits_{p ~\text{простое}} p^{\max\limits(\alpha_p,\, \beta_p)}.

Пусть $d = \prod\limits_p p^{\min\limits(\alpha_p, \beta_p)}$ . Для любого простого $p$ имеем $\min\limits(\alpha_p, \beta_p) \le \alpha_p$ и $\min\limits(\alpha_p, \beta_p) \le \beta_p$ , следовательно, $d \divides a$ и $d \divides b$ , то есть $d$ — общий делитель чисел $a$ и $b$ .

Пусть теперь $c$ — произвольный общий делитель $a$ и $b$ . Тогда каноническое разложение $c$ имеет вид $c = \prod\limits_p p^{\gamma_p}$ с $\gamma_p \le \alpha_p$ и $\gamma_p \le \beta_p$ для всех $p$ . Отсюда $\gamma_p \le \min\limits(\alpha_p, \beta_p)$ для всех $p$ , а значит, $c \divides d$ . Следовательно, $d$ — наибольший общий делитель, то есть $d = \gcd(a, b)$ .

Аналогично, положим $m = \prod\limits_p p^{\max\limits(\alpha_p, \beta_p)}$ . Поскольку $\max\limits(\alpha_p, \beta_p) \ge \alpha_p$ и $\max\limits(\alpha_p, \beta_p) \ge \beta_p$ для всех $p$ , то $a \divides m$ и $b \divides m$ , то есть $m$ — общее кратное.

Пусть $k$ — произвольное общее кратное $a$ и $b$ . Тогда $\alpha_p \le \kappa_p$ и $\beta_p \le \kappa_p$ , где $k = \prod\limits_p p^{\kappa_p}$ . Следовательно, $\max\limits(\alpha_p, \beta_p) \le \kappa_p$ для всех $p$ , то есть $m \divides k$ . Значит, $m$ — наименьшее общее кратное, то есть $m = \lcm(a, b)$ .

Упражнения

Реализовать алгоритм Евклида. Вычислить его асимтотику. Найти при каких числах возникает худший случай для алгоритма Евклида.

Есть число $n$ . Необходимо написать программу, которая позволяет найти сумму количества простых делителей всех соствных чисел $k$ таких, что $k < n$ .