Путеводитель для влюбленных в математику

Теперь мы обобщим этот пример и построим алгоритм вычисления наибольшего общего делителя для двух целых положительных чисел. Нам даны два целых положительных числа a, b, и мы хотим определить НОД (a, b). При этом a больше b. Мы должны вычесть b из a как можно большее число раз. Чтобы выяснить, сколько именно, поделим a на b. Мы получим частное q и остаток c. На языке алгебры:

a – qb = c.

Если окажется, что b – делитель a, тогда остаток будет равен нулю. В ином случае c больше нуля и меньше b (если бы c оказалось больше b, мы смогли бы вычесть b из a еще раз[135]).

Теперь предположим, что d – общий делитель a и b. Тогда

a = xd, b = yd,

где x и y – целые числа. Следовательно,

c = a – qb = xd – q (yd) = (x – qy) d,

и c тоже без остатка делится на d (потому что x – qy входит в множество целых чисел).

С другой стороны, если e – общий делитель b и c, тогда

b = ue, c = ve,

где u и v – целые числа. Следовательно,

a = c + qb = ve + q (ue) = (v + qu) e,

и e – еще и делитель a.

Итак, мы доказали, что общие делители a и b совпадают с общими делителями b и c. Таким образом,

НОД (a, b) = НОД (b, c). (C)

Посмотрим, как тождество (C) позволит нам эффективно вычислить наибольший общий делитель двух больших целых чисел: a = 10 693 и b = 2220.

Мы делим a на b и видим, что 2220 умещается в 10 693 четыре раза[136], при этом остаток c = 1813. Следовательно,

НОД (10 693, 2220) = НОД (2220, 1813).

Переходим к следующей итерации. Введем обозначения a' = 2220 и b' = 1813. Поделим a' на b' и увидим, что 1813 умещается в 2220 всего один раз[137] и остаток c' = 407. На основании тождества (C)

НОД (10 693, 2220) = НОД (2220, 1813) = НОД (1813, 407).

На новом шаге a'' = 1813 и b'' = 407. После деления мы обнаружим, что 407 умещается внутри 1817 четыре раза[138] и остаток c'' = 185. Опять-таки на основании (C)

НОД (10 693, 2220) = НОД (2220, 1813) = НОД (1813, 407) = НОД (407, 185).

На сей раз мы имеем дело с числами a''' = 407 и b''' = 185. Деление показывает, что 185 умещается внутри 407 два раза[139] и остаток равен c''' = 37. Таким образом,

НОД (10 693, 2220) = НОД (2220, 1813) = НОД (1813, 407) = НОД (407, 185) = НОД (185, 37).

Мы почти у цели! Делим a'''' = 185 на b'''' = 37 и – подумать только! – получаем ровно 5. Следовательно, НОД (185, 37) = 37. Завершаем наши выкладки:

НОД (10 693, 2220) = НОД (2220, 1813) = НОД (1813, 407) = НОД (407, 185) = НОД (185, 37) = 37.

Мы нашли наибольший общий делитель 10693 и 2220, проделав всего пять операций деления!

Алгоритм Евклида для поиска наибольшего общего делителя[140] можно сформулировать так:

Поиск НОД: алгоритм Евклида

На входе: два положительных целых числа a и b.

На выходе: НОД (a, b).

1. Найти частное q и остаток c при делении a на b.

2. Если c = 0, то НОД (a, b) = b.

3. В противном случае вычислить НОД (b, c) = НОД (a, b).

Проверьте, насколько хорошо вы усвоили алгоритм Евклида, и вычислите НОД (1309, 1105). Можете воспользоваться калькулятором. Сверьтесь с ответом в конце главы.

Наименьшее общее кратное

Концепция наибольшего общего делителя тесно связана с концепцией наименьшего общего кратного. Для двух положительных целых чисел (допустим, 10 и 15) наименьшее общее кратное – это самое маленькое положительное целое число, которое делится на то и на другое; в нашем случае ответ равен 30. Мы будем использовать обозначение НОК (a, b).

Наименьшее общее кратное полезно при сложении дробей. Например, для сложения 1/10 и 1/15 вначале нужно привести обе дроби к общему знаменателю. Это может быть любое число, которое делится на 10 и на 15; проще всего найти НОК. Так как НОК (10, 15) = 30, то

Найти наименьшее общее кратное для маленьких чисел не слишком сложно, но как быть с большими числами? Скажем, чему равно наименьшее общее кратное 364 и 286?

Один вариант состоит в том, чтобы последовательно выписывать числа, кратные первому и второму, и уповать, что рано или поздно они совпадут[141]:

числа, кратные 364 → 364, 728, 1092, 1456, 1820, 2184, …

числа, кратные 286 → 286, 572, 858, 1144, 1430, 1716, 2002, …

Вскоре мы дойдем до 4004 и запишем ответ: НОК (364, 286) = 4004.

Вот еще одна идея. Разложим 364 и 286 на простые множители:

364 = 2 × 2 × 7 × 13;

286 = 2 × 11 × 13.