Часть I · Числа Глава 4 из 60
Делимость и алгоритм Евклида
Головоломки про календарь, длинное число, плитку, кувшины и монеты — и один ответ на все: наибольший общий делитель и способ найти его, которому больше двух тысяч лет.
Опирается на: 3 · Простые числа
Вы научитесь
- понимать, почему работают признаки делимости, и придумывать новые
- находить НОД и НОК разложением и алгоритмом Евклида, даже для больших чисел
- решать в целых числах уравнения ax + by = c и задачи про кувшины и монеты
В конце прошлой главы мы застряли на дроби $\frac{391}{527}$. Сократить её хочется, но на что? Ни на $2$, ни на $3$, ни на $5$ числа не делятся, а раскладывать их на простые множители долго. Для чисел в несколько сотен цифр — безнадёжно долго даже для компьютера. Нужен способ найти общий делитель, не разлагая чисел.
Такой способ есть, и ему больше двух тысяч лет. Но подойдём к нему не сразу. Эта глава — сборник головоломок: про календарь, про длинное число, про плитку, про кувшины и про монеты. Каждая сначала кажется самостоятельной, а потом сводится к одному и тому же вопросу: какое наибольшее число делит оба данных?
Задача про календарь
Сегодня понедельник. Какой день недели будет через тысячу дней?
Листать календарь не нужно. Дни недели повторяются через семь, поэтому каждые полные семь дней можно выбросить: через $7$, $14$ или $994$ дня снова будет понедельник. Разделим $1000$ на $7$ с остатком: $1000 = 7 \cdot 142 + 6$. Сто сорок две полные недели ничего не меняют, а шесть дней после понедельника — это воскресенье.
Всё, что понадобилось, — остаток. С ним вы знакомы с младших классов, но теперь запишем его точно, потому что вся глава стоит на этой записи.
Разделить с остатком целое $a$ на натуральное $b$ — значит найти целые $q$ и $r$, для которых $a = bq + r$ и $0 \le r < b$. Такая пара всегда есть и всегда одна. Число $r$ называют остатком; если $r = 0$, то $a$ делится на $b$ нацело, и $b$ — делитель $a$ в смысле прошлой главы.
Для любого целого $a$ и натурального $b$ существуют целые $q$ и $r$, для которых $a = bq + r$ и $0 \le r < b$, и такая пара только одна.
Идея: отметить на числовой прямой все кратные $b$ и посмотреть, между какими из них попало $a$.
С отрицательными делимыми многие путаются. В математике остаток всегда берут неотрицательным, и это удобно. Какой день недели был за $17$ дней до понедельника? Запишем $-17 = 7 \cdot (-3) + 4$: отступить на семнадцать дней — всё равно что отступить на три полные недели, а потом пройти четыре дня вперёд. Понедельник плюс четыре дня — пятница. Проверим иначе: семнадцать дней — это две недели и ещё три дня, а за три дня до понедельника тоже была пятница.
Сегодня среда. Какой день недели будет через $100$ дней?
$100 = 7 \cdot 14 + 2$. Четырнадцать недель можно выбросить, остаются два дня: среда, четверг, пятница.
Задача про длинное число
Делится ли $123\,456\,789$ на $9$? А на $11$? А на $7$?
На девять — да, и это можно сказать сразу: сумма цифр $1 + 2 + \dots + 9 = 45$ делится на $9$. Признаки делимости знакомы всем со школы, но их обычно дают как фокусы, без объяснения. А объяснение простое, и оно же подсказывает, как придумать признак для любого делителя.
Запишем число по разрядам (мы уже делали это в главе о счёте):
$$\begin{aligned} 123\,456\,789 = 1 \cdot 10^8 &+ 2 \cdot 10^7 + 3 \cdot 10^6 + \dots \\ &+ 7 \cdot 10^2 + 8 \cdot 10 + 9. \end{aligned}$$Нам понадобится простое свойство остатков: остаток суммы и произведения зависит только от остатков слагаемых и множителей.
Числа $x$ и $x'$ дают одинаковые остатки при делении на $d$ тогда и только тогда, когда $d$ делит разность $x - x'$. Если $x$ и $x'$ дают одинаковые остатки, и $y$ и $y'$ тоже, то одинаковые остатки дают и суммы $x + y$ и $x' + y'$, и произведения $xy$ и $x'y'$.
Если $x = dq + r$ и $x' = dq' + r$ с одним и тем же остатком $r$, то $x - x' = d(q - q')$ делится на $d$. Обратно, пусть $x - x' = dk$ и $x' = dq' + r'$, $0 \le r' < d$. Тогда $x = d(q' + k) + r'$ — это деление $x$ с остатком, и по единственности остаток $x$ тоже $r'$.
Теперь суммы: $(x + y) - (x' + y') = (x - x') + (y - y')$ — сумма двух кратных $d$, и она делится на $d$. Произведения: $xy - x'y' = x(y - y') + y'(x - x')$, и оба слагаемых делятся на $d$. По первой части остатки совпадают.
Теперь сам признак — сразу для любого делителя $d$.
Пусть число $n = a_m 10^m + \dots + a_1 \cdot 10 + a_0$, и $w_k$ — число, которое отличается от $10^k$ на кратное $d$ (например, остаток от деления $10^k$ на $d$). Тогда $n$ и сумма $S = a_m w_m + \dots + a_1 w_1 + a_0 w_0$ дают одинаковые остатки при делении на $d$. В частности, $n$ делится на $d$ тогда и только тогда, когда $S$ делится на $d$.
Вычтем: $n - S = a_m (10^m - w_m) + \dots + a_1 (10 - w_1) + a_0 (1 - w_0)$. Каждая скобка по условию делится на $d$, значит, делится и вся сумма. По лемме об остатках $n$ и $S$ дают одинаковые остатки; остаток $0$ у одного означает остаток $0$ у другого.
Для девятки веса самые простые: $10 = 9 + 1$, $100 = 99 + 1$, $1000 = 999 + 1$, и каждая степень десяти даёт остаток $1$.
Число и сумма его цифр дают одинаковые остатки при делении на $9$ и при делении на $3$. Поэтому число делится на $9$ (на $3$) тогда и только тогда, когда на $9$ (на $3$) делится сумма его цифр.
Идея: в каждой сотне и в каждом десятке прячется кратное девяти и одна «лишняя» клетка, а лишние клетки вместе с единицами — это сумма цифр. Покажем на числе $234$; для любого числа рассуждение то же.
С одиннадцатью похоже, только $10 = 11 - 1$.
Число делится на $11$ тогда и только тогда, когда на $11$ делится знакочередующаяся сумма его цифр $a_0 - a_1 + a_2 - a_3 + \dots$, начиная с последней.
Числа $10$ и $-1$ дают одинаковые остатки при делении на $11$: их разность $11$. По лемме об остатках произведения тоже дают одинаковые остатки, поэтому $10^k = 10 \cdot 10 \cdots 10$ и $(-1)^k$ отличаются на кратное $11$. Значит, в признаке по весам можно взять $w_k = (-1)^k$: веса $1, -1, 1, -1, \dots$ Сумма $S$ с такими весами и есть знакочередующаяся сумма цифр. Для нашего числа: $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$. Остаток $5$, так что на $11$ число $123\,456\,789$ не делится.
Так получаются и остальные школьные признаки.
Число делится на $2$ или на $5$ тогда и только тогда, когда на $2$ (на $5$) делится его последняя цифра; на $4$ или на $25$ — когда на $4$ (на $25$) делится число из двух последних цифр; на $8$ или на $125$ — когда на $8$ (на $125$) делится число из трёх последних цифр.
Воспользуемся признаком по весам. Число $10$ делится на $2$ и на $5$, поэтому $10^k$ при $k \ge 1$ делится на них тоже, и можно взять $w_k = 0$ для всех разрядов, кроме последнего ($w_0 = 1$): сумма $S$ равна последней цифре. Число $100 = 4 \cdot 25$ делится на $4$ и на $25$, и все $10^k$ при $k \ge 2$ тоже; берём $w_0 = 1$, $w_1 = 10$, остальные веса нулевые — $S$ равна числу из двух последних цифр. Так же $1000 = 8 \cdot 125$ даёт признак по трём последним цифрам.
Для $7$ веса идут по кругу: $1, 3, 2, -1, -3, -2$. Признак делимости на семь существует, но запомнить его труднее, чем просто разделить.
Число делится на $3$, если сумма его цифр делится на $3$. Верно ли, что число делится на $6$, если сумма его цифр делится на $6$?
У $15$ сумма цифр $6$, но $15$ на $6$ не делится. Признак суммы цифр работает только для делителей девятки, $3$ и $9$: только для них $10$ даёт остаток $1$. При делении на $6$ десятка даёт остаток $4$, и сумма цифр ничего не говорит. Правильный признак для $6$ — число делится на $2$ и на $3$ одновременно.
Задача про плитку
Пол прихожей имеет размер $336 \times 480$ сантиметров. Его хотят выложить одинаковыми квадратными плитками, не разрезая ни одной. Какую самую крупную плитку можно взять?
Сторона плитки должна укладываться целое число раз и вдоль $336$, и вдоль $480$, то есть делить оба числа. Нужен их наибольший общий делитель. Разложим числа на простые множители, как в прошлой главе:
$$336 = 2^4 \cdot 3 \cdot 7, \qquad 480 = 2^5 \cdot 3 \cdot 5.$$Общий делитель может содержать только простые, которые есть в обоих числах, и не больше раз, чем в каждом. Двоек — не больше четырёх, троек — не больше одной, семёрок и пятёрок — ни одной. Самый крупный такой делитель — $2^4 \cdot 3 = 48$. Плитка $48 \times 48$, по $7$ штук в ширину и $10$ в длину.
Наибольший общий делитель чисел $a$ и $b$ — самое большое число, на которое делятся оба. Обозначение: $\text{НОД}(a, b)$; в международной литературе пишут $\gcd(a, b)$ (от английского greatest common divisor). Если $\text{НОД}(a, b) = 1$, числа называют взаимно простыми: у них нет общих делителей, кроме единицы.
Вторая половина задачи — про повторения. Один маяк вспыхивает каждые $12$ секунд, другой каждые $18$. Сейчас они вспыхнули вместе. Когда это случится снова? Нужно число, которое делится и на $12$, и на $18$, причём наименьшее. Снова раскладываем: $12 = 2^2 \cdot 3$, $18 = 2 \cdot 3^2$. Теперь каждое простое надо взять столько раз, сколько его в каждом из чисел, то есть по максимуму: $2^2 \cdot 3^2 = 36$. Через $36$ секунд.
Наименьшее общее кратное $\text{НОК}(a, b)$ — самое маленькое натуральное число, которое делится и на $a$, и на $b$ (в английской литературе $\operatorname{lcm}(a, b)$).
То, что мы сделали с плиткой и маяками, работает всегда.
Пусть $a = p_1^{a_1} \cdots p_k^{a_k}$ и $b = p_1^{b_1} \cdots p_k^{b_k}$ (выписаны все простые, входящие хотя бы в одно из чисел; показатель $0$ означает, что простого в числе нет). Тогда $\text{НОД}(a, b) = p_1^{\min(a_1, b_1)} \cdots p_k^{\min(a_k, b_k)}$ и $\text{НОК}(a, b) = p_1^{\max(a_1, b_1)} \cdots p_k^{\max(a_k, b_k)}$. Более того, каждый общий делитель $a$ и $b$ делит их НОД, а каждое общее кратное делится на НОК.
В главе о простых мы выяснили, как устроены делители: по единственности разложения $d$ делит $a$ тогда и только тогда, когда $d = p_1^{c_1} \cdots p_k^{c_k}$ с $c_i \le a_i$ для каждого $i$. Поэтому $d$ — общий делитель, когда $c_i \le a_i$ и $c_i \le b_i$, то есть $c_i \le \min(a_i, b_i)$. Наибольший такой делитель получится, если взять каждый показатель наибольшим, $c_i = \min(a_i, b_i)$, — это и есть формула для НОД. А каждый общий делитель, у которого $c_i \le \min(a_i, b_i)$, делит это число.
С кратными так же: $m$ делится на $a$ тогда и только тогда, когда каждое $p_i$ входит в $m$ не меньше $a_i$ раз. Общее кратное должно содержать $p_i$ не меньше $\max(a_i, b_i)$ раз; наименьшее такое число — произведение $p_i^{\max(a_i, b_i)}$ (другие простые только увеличили бы его), и каждое общее кратное на него делится.
Для любых натуральных $a$ и $b$ выполнено $\text{НОД}(a, b) \cdot \text{НОК}(a, b) = a \cdot b$.
По предыдущему утверждению в произведение $\text{НОД} \cdot \text{НОК}$ каждое простое $p_i$ входит $\min(a_i, b_i) + \max(a_i, b_i)$ раз. Из двух чисел $a_i$ и $b_i$ одно — минимум, другое — максимум, поэтому $\min(a_i, b_i) + \max(a_i, b_i) = a_i + b_i$. Столько же раз $p_i$ входит в $a \cdot b$. У двух чисел одинаковые разложения, значит, это одно и то же число.
Формула полезна тем, что НОК считать почти не нужно: хватит НОД. Дальше мы научимся находить НОД без всякого разложения, а НОК тогда получится делением.
Чему равно $\text{НОК}(12, 18)$?
$12 \cdot 18 = 216$ — общее кратное, но не наименьшее: делится на оба числа и $36$. По формуле $\text{НОК} = \frac{12 \cdot 18}{\text{НОД}(12, 18)} = \frac{216}{6} = 36$. Произведение равно НОК только для взаимно простых чисел.
Задача про дробь
Вернёмся к $\frac{391}{527}$. Раскладывать мы не хотим. Зато есть наблюдение, простое до неловкости: если число делит и $527$, и $391$, то оно делит и их разность $527 - 391 = 136$. И наоборот, общий делитель $391$ и $136$ делит их сумму $527$. Значит, у пар $(527, 391)$ и $(391, 136)$ одни и те же общие делители, а потому и один и тот же наибольший.
Большое число мы заменили меньшим, и задача не изменилась. Можно продолжать: вычитать меньшее из большего, пока получается. Удобнее вычитать сразу столько раз, сколько влезет, то есть делить с остатком.
Если $a = bq + r$, то общие делители чисел $a$ и $b$ — те же самые, что у чисел $b$ и $r$. В частности, $\text{НОД}(a, b) = \text{НОД}(b, r)$.
Идея Евклида: общий делитель — это общая мера. Если мерка $d$ укладывается целое число раз и в $a$, и в $b$, она укладывается и в то, что остаётся от $a$ после вычитания нескольких $b$.
Доведём дело до конца:
$$\begin{aligned} 527 &= 1 \cdot 391 + 136, \\ 391 &= 2 \cdot 136 + 119, \\ 136 &= 1 \cdot 119 + 17, \\ 119 &= 7 \cdot 17 + 0. \end{aligned}$$Последний ненулевой остаток — $17$. Это и есть $\text{НОД}(527, 391)$, и дробь сокращается: $\frac{391}{527} = \frac{23 \cdot 17}{31 \cdot 17} = \frac{23}{31}$. Четыре деления, и ни одного разложения.
Алгоритм Евклида находит $\text{НОД}(a, b)$: делим большее число на меньшее с остатком, затем меньшее — на остаток, затем первый остаток — на второй, и так далее. Когда деление пройдёт без остатка, последний делитель — искомый НОД.
Почему алгоритм всегда заканчивается и почему в конце получается именно НОД? У этого есть наглядная картинка: прямоугольник, от которого отрезают квадраты.
Для любых натуральных $a > b$ алгоритм Евклида заканчивается после конечного числа делений, и последний ненулевой остаток (или само $b$, если $a$ делится на $b$) равен $\text{НОД}(a, b)$.
Идея: деление с остатком — это отрезание квадратов от прямоугольника, а прямоугольник с целыми сторонами не может уменьшаться бесконечно.
Ниже тот же прямоугольник можно резать самостоятельно — в том числе $527 \times 391$ из нашей дроби, — и посмотреть, что будет, если стороны вообще не имеют общей меры.
Найдите $\text{НОД}(1071, 462)$ алгоритмом Евклида.
$1071 = 2 \cdot 462 + 147$, $462 = 3 \cdot 147 + 21$, $147 = 7 \cdot 21 + 0$. Последний ненулевой остаток — $21$. Проверка: $1071 = 21 \cdot 51$, $462 = 21 \cdot 22$, и $\text{НОД}(51, 22) = 1$.
Насколько быстр алгоритм? Остатки убывают, но может ли их быть очень много? Ответ дал Габриэль Ламе в 1844 году.
Если меньшее из двух чисел записывается $k$ цифрами, алгоритм Евклида делает не больше $5k$ делений.
Доказательство теоремы Ламе: самые «неудобные» пары — числа Фибоначчи
Идея: алгоритм работает дольше всего, когда каждое неполное частное равно $1$, и тогда числа растут, если идти от конца к началу, не медленнее чисел Фибоначчи $F_1 = 1$, $F_2 = 1$, $F_3 = 2$, $F_4 = 3$, $5, 8, 13, \dots$, где каждое число — сумма двух предыдущих (подробно о них — в главе о последовательностях).
Пусть алгоритм на паре $a > b$ сделал $n$ делений. Выпишем числа, которые в нём встречаются: $u_0 = a > u_1 = b > u_2 > \dots > u_n > u_{n+1} = 0$, где $i$-е деление — это $u_{i-1} = q_i u_i + u_{i+1}$. Последний ненулевой остаток $u_n \ge 1 = F_2$, а $u_{n-1} > u_n$, поэтому $u_{n-1} \ge 2 = F_3$. Каждое неполное частное $q_i \ge 1$, значит, $u_{i-1} \ge u_i + u_{i+1}$: каждое число не меньше суммы двух следующих. Поднимаясь от конца, получаем $u_{n-2} \ge F_3 + F_2 = F_4$, $u_{n-3} \ge F_5$, и вообще $u_{n-j} \ge F_{j+2}$. При $j = n - 1$: $b = u_1 \ge F_{n+1}$.
Числа Фибоначчи растут не медленнее степеней числа $\varphi = \frac{1 + \sqrt5}{2} \approx 1{,}618$: $F_m \ge \varphi^{m-2}$. Для $m = 2$ и $m = 3$ это видно ($1 \ge 1$, $2 \ge 1{,}618$), а дальше по цепочке: $F_{m+1} = F_m + F_{m-1} \ge \varphi^{m-2} + \varphi^{m-3} = \varphi^{m-3}(\varphi + 1) = \varphi^{m-1}$, потому что $\varphi + 1 = \varphi^2$ (проверьте: $\varphi^2 = \frac{6 + 2\sqrt5}{4} = \varphi + 1$). Итак, $b \ge F_{n+1} \ge \varphi^{n-1}$.
Если у $b$ ровно $k$ цифр, то $b < 10^k$. А $\varphi^5 \approx 11{,}09 > 10$, поэтому $10^k < \varphi^{5k}$. Получаем $\varphi^{n-1} < \varphi^{5k}$, то есть $n - 1 < 5k$ и $n \le 5k$.
Оценка точная: для пары $(13, 8)$ нужно пять делений, для $(144, 89)$ — десять, для $(1597, 987)$ — пятнадцать.
Для трёхзначных чисел — не больше пятнадцати делений, для двадцатизначных — не больше ста. Разложение двадцатизначного числа на множители перебором заняло бы миллиарды делений. Теорему Ламе часто называют одним из первых в истории анализов того, сколько работы требует алгоритм.
Потренируйтесь. На первом уровне числа небольшие и раскладываются легко, на втором — такие, что без Евклида не обойтись. Если задача не сходится, решатель покажет алгоритм по шагам.
Задача про кувшины
У фонтана стоят два кувшина, на $3$ и на $5$ литров, других мерок нет. Как отмерить ровно $4$ литра? Именно эту задачу решают герои Брюса Уиллиса и Сэмюэла Л. Джексона в фильме «Крепкий орешек 3: Возмездие» (1995), только в галлонах и под тиканье бомбы. Задачи о переливании много старше: их разбирал ещё Никколо Тарталья в XVI веке.
Кувшины на $3$ и $5$ литров дают любое целое количество от $0$ до $5$. А кувшинами на $6$ и $10$ литров пять литров не отмерить, сколько ни старайся. Почему? Сначала в обоих кувшинах пусто. Наполнив кувшин, получаем $6$ или $10$ литров — чётное число. Выливая, получаем ноль. Переливая, мы переносим либо всё содержимое одного кувшина, либо столько, сколько не хватает до полного другого, — и то и другое чётно, если до этого в кувшинах было чётное количество. Значит, в каждом кувшине всегда чётное число литров: все объёмы делятся на $\text{НОД}(6, 10) = 2$. А пять на два не делится.
Всякий объём, который появляется в кувшинах, имеет вид $3x + 5y$ с целыми $x$ и $y$: так записываются полные кувшины, а переливание и выливание только складывают и вычитают такие числа. Например, $4 = 3 \cdot 3 + 5 \cdot (-1)$: трижды наполнить малый кувшин, каждый раз переливая его в большой, и один раз вылить полный большой. Кувшины — прибор, который строит такие суммы. Какие числа вообще можно записать в виде $ax + by$?
Для любых натуральных $a$ и $b$ найдутся целые $x$ и $y$ (одно из них, как правило, отрицательное), для которых $ax + by = \text{НОД}(a, b)$.
Идея: проследить за алгоритмом Евклида и заметить, что каждый его остаток складывается из $a$ и $b$ с целыми множителями.
Соотношение Безу — запись наибольшего общего делителя в виде $ax + by$ с целыми $x$ и $y$. Оно носит имя Этьена Безу (XVIII век), доказавшего похожее утверждение для многочленов; для целых чисел его знал ещё Клод Гаспар Баше де Мезириак, собиратель занимательных задач начала XVII века.
Найти $x$ и $y$ помогает тот же алгоритм Евклида, пройденный в обратную сторону. Каждое его равенство выражает остаток через два предыдущих числа.
Пример: соотношение Безу для 527 и 391
Выпишем равенства алгоритма так, чтобы слева стоял остаток: $136 = 527 - 391$, $119 = 391 - 2 \cdot 136$, $17 = 136 - 119$. Начнём с последнего и будем подставлять предыдущие:
$$\begin{aligned} 17 &= 136 - 119 \\ &= 136 - (391 - 2 \cdot 136) \\ &= 3 \cdot 136 - 391 \\ &= 3 \cdot (527 - 391) - 391 \\ &= 3 \cdot 527 - 4 \cdot 391. \end{aligned}$$Проверка: $3 \cdot 527 = 1581$, $4 \cdot 391 = 1564$, разность $17$.
Такую процедуру называют расширенным алгоритмом Евклида.
Уравнение $ax + by = c$ с натуральными $a$, $b$ и целым $c$ имеет решение в целых числах тогда и только тогда, когда $c$ делится на $\text{НОД}(a, b)$.
Обозначим $d = \text{НОД}(a, b)$; нужно доказать два направления.
Если решение есть, то $d$ делит $a$, а значит, и $ax$; так же $d$ делит $by$. Тогда $d$ делит и сумму $ax + by = c$.
Наоборот, пусть $c$ делится на $d$: $c = d \cdot t$. По соотношению Безу найдутся целые $x_0$, $y_0$ с $ax_0 + by_0 = d$. Умножим это равенство на $t$: $a(x_0 t) + b(y_0 t) = dt = c$. Пара $x = x_0 t$, $y = y_0 t$ — решение.
Уравнения, которые нужно решить именно в целых числах, называют диофантовыми — в честь Диофанта Александрийского (около III века н. э.), автора «Арифметики». Сам Диофант, впрочем, чаще искал рациональные решения, но имя закрепилось.
Вернёмся к кувшинам и ответим на вопрос полностью.
Кувшинами на $a$ и $b$ литров, где $a \le b$, можно отмерить $c$ литров ($0 < c \le b$) тогда и только тогда, когда $c$ делится на $\text{НОД}(a, b)$.
Обозначим $d = \text{НОД}(a, b)$.
Необходимость. Покажем, что в каждом кувшине всегда кратное $d$ литров. Вначале там по нулю. Наполнив кувшин, получаем $a$ или $b$ литров — кратное $d$. Вылив, получаем ноль. При переливании переходит либо всё содержимое одного кувшина, либо столько, сколько не хватает другому до полного, то есть ёмкость минус содержимое. Если до этого в обоих кувшинах были кратные $d$, то и переливаемое количество, и новые содержимые — кратные $d$. Значит, объём, не кратный $d$, не появится никогда.
Достаточность. Если $c = b$, просто наполним большой кувшин. Пусть $c < b$ и $c = dt$. Будем действовать по одному правилу: если малый кувшин пуст — наполняем его; переливаем из малого в большой; если большой наполнился — выливаем его и продолжаем переливать. Когда в большой кувшин перейдёт вода из $k$ наполненных малых, в нём окажется остаток от деления $ka$ на $b$: всего туда попало $ka$ литров, а выливали мы его каждый раз полным, по $b$ литров. Осталось найти $k$, при котором этот остаток равен $c$. По соотношению Безу $ax + by = d$ с целыми $x$, $y$; умножим на $t$: $a \cdot xt = c - b \cdot yt$. Прибавим к $xt$ достаточно большое кратное $b$, чтобы получилось натуральное число $k = xt + bm$. Тогда $ka = c + b(am - yt)$, и так как $0 \le c < b$, по единственности деления с остатком остаток от деления $ka$ на $b$ равен $c$. После $k$-го малого кувшина в большом будет ровно $c$ литров.
Для кувшинов $3$ и $5$ годится любой объём до пяти литров, для $6$ и $10$ — только чётный.
Какой наименьший ненулевой объём можно отмерить кувшинами на $9$ и $12$ литров?
Все объёмы имеют вид $9x + 12y$ и делятся на $\text{НОД}(9, 12) = 3$, а сам НОД по соотношению Безу получить можно: $9 \cdot (-1) + 12 \cdot 1 = 3$ — наполнить большой кувшин и перелить из него в малый. Ответ: $3$ литра.
Лемма Евклида ещё раз
В главе о простых числах лемма Евклида была доказана без всяких НОД, через наименьшее «подходящее» число. Соотношение Безу даёт доказательство в две строки — и сразу более общего утверждения, которое понадобится нам для монет.
Если $a$ делит произведение $bc$ и $\text{НОД}(a, b) = 1$, то $a$ делит $c$.
По соотношению Безу $ax + by = 1$ для каких-то целых $x$, $y$. Умножим на $c$: $acx + bcy = c$. Первое слагаемое делится на $a$, потому что содержит множитель $a$; второе — потому что $a$ делит $bc$. Значит, $a$ делит и их сумму $c$.
Если простое число $p$ делит произведение $bc$, то $p$ делит $b$ или $p$ делит $c$.
Пусть $p$ не делит $b$. Общий делитель $p$ и $b$ — делитель простого $p$, то есть $1$ или $p$; но $p$ не делит $b$, значит, $\text{НОД}(p, b) = 1$. По обобщённой лемме $p$ делит $c$.
Лемма у Евклида стоит в VII книге под номером 30 — в той же книге, что и алгоритм. На ней держится единственность разложения на простые множители из прошлой главы. А в «мире Гильберта» из той главы числа нельзя вычитать, не выходя из мира ($9 - 5 = 4$ туда не входит), поэтому нет ни алгоритма Евклида, ни соотношения Безу — и единственность рушится.
Задача про монеты
В стране ходят только монеты по $3$ и по $5$ рублей. Какие суммы можно заплатить без сдачи?
Переберём: $3$, $5$, $6 = 3 + 3$, $8 = 3 + 5$, $9$, $10$, $11 = 3 + 3 + 5$, $12$, $13 = 3 + 5 + 5$… Не получаются $1$, $2$, $4$ и $7$. А начиная с восьми подходит всё: $8$, $9$ и $10$ набираются, а дальше достаточно добавлять по трёшке. Любые три подряд идущие суммы, которые удалось набрать, тянут за собой все следующие.
Пусть натуральные $a$ и $b$ взаимно просты. Тогда каждое целое число, большее $ab - a - b$, можно записать в виде $ax + by$ с целыми неотрицательными $x$ и $y$, а само $ab - a - b$ — нельзя.
Идея: разложить все суммы по $a$ столбцам — по остатку от деления на $a$ — и найти в каждом столбце первую сумму, которую удаётся набрать.
Эту задачу называют задачей Фробениуса, по имени немецкого математика Фердинанда Георга Фробениуса, который, как рассказывают, любил предлагать её на лекциях. Для двух монет ответ был известен Джеймсу Сильвестру в 1880-х годах. Он же нашёл, сколько всего сумм нельзя набрать.
Если $a$ и $b$ взаимно просты, то монетами $a$ и $b$ нельзя набрать ровно $\frac{(a - 1)(b - 1)}{2}$ сумм — половину чисел от $0$ до $ab - a - b$.
Доказательство: суммы разбиваются на пары
Идея: разбить числа от $0$ до $g = ab - a - b$ на пары $n$ и $g - n$ и показать, что в каждой паре набирается ровно одно.
По второму шагу доказательства теоремы Фробениуса каждое целое $n$ единственным образом записывается как $n = xa + yb$ с целым $x$ и $0 \le y \le a - 1$: $yb$ — отмеченное число столбца, в котором стоит $n$, а $x$ — на сколько клеток $n$ ниже него (отрицательное $x$ — выше). По четвёртому шагу $n$ набирается ровно тогда, когда $x \ge 0$.
Для второго числа пары: $g - n = ab - a - b - xa - yb = (-x - 1)a + (a - 1 - y)b$, и снова $0 \le a - 1 - y \le a - 1$. Значит, для $g - n$ роль $x$ играет $-x - 1$, а это число неотрицательно ровно тогда, когда $x$ отрицательно. Из двух чисел пары набирается ровно одно.
Чисел от $0$ до $g$ всего $g + 1 = (a - 1)(b - 1)$. Это число чётное (из взаимно простых $a$ и $b$ хотя бы одно нечётно, и соответствующий множитель $a - 1$ или $b - 1$ чётен), поэтому $n$ и $g - n$ никогда не совпадают, и числа разбиваются на $\frac{(a - 1)(b - 1)}{2}$ пар. В каждой паре одно число не набирается, а больше $g$ ненабираемых нет. Для монет $3$ и $5$ это четыре суммы: $1$, $2$, $4$ и $7$.
В ходу монеты по $5$ и по $7$ рублей. Какую наибольшую сумму ими нельзя заплатить без сдачи?
$\text{НОД}(5, 7) = 1$, поэтому формула работает: $5 \cdot 7 - 5 - 7 = 23$. Проверка: $23$, $23 - 7 = 16$, $23 - 14 = 9$, $23 - 21 = 2$ — ни одно не делится на $5$, так что $23$ не набрать. А $24 = 5 \cdot 2 + 7 \cdot 2$, $25 = 5 \cdot 5$, $26 = 5 + 7 \cdot 3$, $27 = 5 \cdot 4 + 7$, $28 = 7 \cdot 4$ — пять подряд, дальше добавляем пятёрки.
С тремя номиналами задача становится по-настоящему трудной: формулы такого же простого вида для неё нет. Самый известный пример — куриные наггетсы в «Макдоналдсе», которые когда-то продавали коробками по $6$, $9$ и $20$ штук. Любое количество больше $43$ так купить можно, а ровно $43$ — нельзя. Это число в шутку зовут числом Макнаггетса.
Куда дальше
Мы научились выяснять, делится ли одно число на другое, находить общие делители и кратные, решать уравнения в целых числах. Но не всякое деление проходит нацело. Семь пирогов на троих: каждому по два, и один пирог остаётся. Если мы не хотим, чтобы он пропал, придётся резать его на доли — и заодно понять, что такое $\frac13$ и почему в десятичной записи она никогда не кончается. Это дроби, и НОД с НОК понадобятся там на каждом шагу.