Алгоритм Евклида и основная теорема арифметики

30

В.Н. ВАГУТЕН
Алгоритм Евклиза и основная теорема арифметики

Эта статья написана по материалам экспериментального задания для 8—9-х классов Всесоюзной заочной математической школы Академии педагогических наук СССР при Московском государственном университете имени М. В. Ломоносова.

Все знают, что любое целое положительное число можно разложить в произведение простых множителей; так например,

$$400 = 2^4 \cdot 5^2, \quad 1001 = 7 \cdot 11 \cdot 13, \quad 290981 = 43 \cdot 67 \cdot 101.$$

Почему такое разложение единственно? Более простой факт: если произведение mn делится на 43, то хотя бы одно из чисел m и n должно делиться на 43. Как это доказать?

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

Всюду латинскими буквами (a, b, c, d и т. д.) мы обозначаем целые числа.

1. Дelimность суммы, разности и произведения

Мы говорим, что целое число a делится на целое число b, если существует такое целое число k, что a = kb. В таком случае число b называется делимем числа a.

Сразу выведем два простых утверждения:

1°. Если числа a и b делятся на c, то u их сумма a + b, u их разность a - b делятся на c;
2°. Если a делится на c, a b делится на d, то их произведение ab делится на cd.

Докажем 1°. Поскольку a делится на c, то a = kc, где k — некоторое целое число. Точно так же b = mc, где m — целое число. Поэтому a + b = (k + m)c, a - b = (k - m)c, откуда следует, что каждое из чисел a + b и a - b делится на c.

Докажем 2°. Пусть a = kc, b = md. Тогда ab = (km)cd, откуда и следует утверждение 2°.

Задча 1. Докажите, что если a делится на b, a b делится на c, то a делится на c.

Задча 2. Какие из следующих утверждения верны, а какие нет:

a) если одно слагаемое делится на 6, а другое не делится на 6, то их сумма не делится на 6;
b) если сумма двух слагаемых не делится на 6, то хотя бы одно из них не делится на 6;
g) если сумма двух слагаемых не делится на 6, то каждое слагаемое не делится на 6;

32

4. Алгоритм Евклида

Для того, чтобы найти НОД двух чисел, можно, конечно, действовать так: выписать все делители каждой из чисел, выбрать общие делители, а затем взять из них наиболее.Можно поступить иначе, не отыскивая отдельно делители каждой из чисел.

Докажем следующую важную lemma.

Лемма 1. Пусть $a = bq + r$, $m=d a$ НОД $(a, b) = \text{НОД}(b, r)$.

С этой целью покажем, что у пары чисел $(a, b)$ множество общих делителей в точности такое же, как у пары чисел $(b, r)$. Отсюда, конечно, будет следовать, что и НОД у этих пар один и тот же. Итак, докажем, что каждый общий делитель чисел $a$ и $b$ является также делителем числа $r$, и наоборот, что каждый общий делитель чисел $b$ и $r$ является делителем числа $a$.

Докажем сначала первое утверждение. Пусть $a$ и $b$ делятся на $k$. Тогда $bq$ делится на $k$ (см. 2° из п. 1) и $r = a - bq$ делится на $k$ (см. 1° из п. 1).

Перейдем ко второму утверждению. Если $b$ и $r$ делятся на $m$, то $bq$ делится на $m$ и $a = bq + r$ делится на $m$ (здесь мы опять пользовались утверждениями 1° и 2° из п. 1).

Доказанная lemma позволяет легко и быстро находить НОД двух чисел. Посмотрим, как это делается.

Пример. Найдем, чему равен НОД (6069, 663).

Решение. Разделим 6069 на 663 с остатком:

$$6069 = 663 \cdot 9 + 102.$$

Из леммы следует, что НОД (6069, 663) = НОД (663, 102).

Ищем НОД (663, 102). Для этого делим 663 на 102:

$$663 = 102 \cdot 6 + 51.$$

Снова, применив lemму, получаем НОД (663, 102) = НОД (102, 51). Но 102 делится на 51 без остатка:

$$102 = 51 \cdot 2,$$

позетом НОД (102, 51) = 51, следовательно,

$$51 = \text{НОД} (102, 51) = \text{НОД} (663, 102) = \text{НОД} (6069, 663).$$

Ответ. НОД (6069, 663) = 51.

Метод отыскания наиболее общого делителя, основанный на последовательном применении леммы 1, носит специальное название — алгоритм Евклида.

Заддача 13. Найдите наиболее общий делитель чисел:

a) 987 654 321 и 123 456 789,
b) 7 777 777 777 и 777 777.

Заддача 14. От прямого линника 324 $cm \times 141$ $cm$ отрезают несколько квадратов со стороны 141 $cm$, пока не остается прямого линника, у которого одна из сторон

Рис. 3.

меньше 141 $cm$. От полученного прямого линника снова отрезают квадраты, стороны которых равны его меньшей стороны, до тех пор, пока это возможно, и так далее (рис. 3).

На какие квадраты будет разрезан прямого линника? (Укажите их размеры и количество).

Итак, алгоритм Евклида — это простой метод нахождения наиболее общого делителя двух чисел. Если у нас имеется два числа $a$ и $b$, причем $a > b > 0$, то сначала делим $a$ на $b$ и получаем остаток $r_1$, который меньше, чем $b$. Затем мы делим число $b$ на $r_1$ и находим остаток $r_2$, который меньше, чем $r_1$. Далее, мы делим число $r_1$ на число $r_2$, при этом получаем остаток $r_3$, меньше, чем $r_2$, и так далее, пока какой-нибудь остаток $r_{n-1}$ не разделится на остаток $r_n$ нацело, без остатка (то есть $r_{n+1} = 0$).

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

34

Решение $x = -6, y = 55$ годится для обих уравнения.

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

Например, числа

$$x = -6 + 13t, y = 55 - 119t$$

($t$ — любое целое число) также являются решениями обих наших уравнений. В самом деле,

$$119 (-6 + 13t) + 13 (55 - 119t) = 1$$
и, конечно,
$$51 \cdot 119 (-6 + 13t) + 51 \cdot 13 (55 - 119t) = 51,$$
то есть
$$6069 (-6 + 13t) + 663 (55 - 119t) = 51.$$

Формулы (*) дают все решения этих уравнений в целых числах. Доказем это. Пусть $(x, y)$ — какое-то решение:

$$119x + 13y = 1.$$

Вычитем из этого уравнения почленно уже известное нам равенство

$$119 \cdot (-6) + 13 \cdot 55 = 1.$$

Получим

$$119 (x + 6) + 13 (y - 55) = 0$$
или

$$119 (x + 6) = 13 (55 - y).$$

Поскольку левая часть последнего равенства делится на 13, а число 119 и 13 взaimно просыпли, то число $x + 6$ должно делиться на 13: $x + 6 = 13t$, где $t$ — некоторое целое число. Тогда $y = 55 - 119t$. Тем самым мы по существу выяснили, как находится решение любого линейного уравнения $ax + by = c$ в целых числах. В общем случае результат таков:

Для того, чтобы уравнение $ax + by = c$ имело решение в целых числах $(x, y)$, необходимо и достаточно, чтобы $c$ делилось на НОД $(a, b) = d$. Если это условие выполняено $u (x_0, y_0)$ — одно из решений этого уравнения, то все его решения задаются формулами

$$x = x_0 + b_1t, y = y_0 - a_1t,$$
$$a_1 = \frac{a}{d}, b_1 = \frac{b}{d}.$$

Задание 16. Найдите такие целые числа $x$ и $y$, что $85x + 204y = 17$.

Задание 17. Имеют ли следующие уравнения решения в целых числах:

a) $105x + 56y = 42$;
b) $104x + 65y = 43$?

Задание 18. a) Можно ли составить батараю напряжением 220 $\theta$, соединяя последовательно элементы двух типов: напряжением $6 \theta$ и $16 \theta$, — и если можно, то сколько надо взять тех и других?

b) Тот же вопрос, если напряжение элементов $6 \theta$ и $15 \theta$.

Задание 19. Можно ли размешать 45 рублей на рублей, трехрублевые и пятрирублевые купюры так, чтобы получить всего 20 купюр?

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

Doоказательства основной теоремы сделаем еще один шаг — доказем лемму.

Лемма 3. Если произведение ab делится на c, причем числа b и c взаимно просты, то a делится на c.

Действительно, поскольку целые числа $x$ и $y$, что $1 = bx + cy$. Умножая обе части равенства на $a$, получаем, что $a = abx + acy$. Так как по условию ab делится на $c$, то и $abx$, и, разумеется, acy делится на $c$, а значит, и их сумма $a$ делится на $c$.

Лемма 3 очень часто используется при решении задачи, причем иногда совсем «незаметно». Мы, например, опирались на нее в предыдущем пункте при выводе формул, дающих все решения уравнения $119x + 13y = 1$ (там мы видели ли соответствующий форму курсивом).

Задание 20. Доказите, что если число $a$ делится на взаимно простые числа $b$ и $c$, то $a$ делится на $bc$.

Задание 21. Какие из следующих утверждений верны:

a) если $ab$ делится на 15, то хотя бы один из компонентей делится на 15;
b) если $ab$ делится на 17, от хотя бы один из компонентей делится на 17;
b) если $a$ делится на 6, а $b$ делится на 10, то $ab$ делится на 15;
g) если $ab$ делится на 60, а $b$ взаимно просто с 10, то $a$ делится на 20.

Напомним теперь, что намуральное число $p$ называется простым, если оно имеет равное деление $p$ и 1.