Краткий ответ
Алгоритм Евклида — это способ найти НОД (наибольший общий делитель) двух натуральных чисел с помощью повторяющегося деления с остатком. Вся идея в одном равенстве:
\[ \text{НОД}(a,b)=\text{НОД}(b,\ a \bmod b) \]
Повторяем замену \((a,b)\to(b,\ a \bmod b)\), пока остаток не станет равен нулю. Тогда второе число (текущее \(b\)) — это и есть НОД.
1. Зачем он нужен
НОД(a, b) — наибольшее число, на которое делятся и \(a\), и \(b\) без остатка. Пример: \(\text{НОД}(48,18)=6\), потому что 6 — самый большой общий делитель.
Перебирать все делители долго. Евклид придумал делать это за несколько шагов.
2. Почему алгоритм работает (главный довод)
Пусть \(a = b\cdot q + r\), где \(r = a \bmod b\) — остаток.
- Если какое-то число \(d\) делит \(a\) и \(b\), то оно делит и \(r = a - b\cdot q\).
- Если \(d\) делит \(b\) и \(r\), то оно делит и \(a = b\cdot q + r\).
Значит у пар \((a,b)\) и \((b,r)\) одни и те же общие делители, поэтому совпадают и наибольшие из них. Замена пары ничего не меняет — это и есть суть метода.
3. Две записи алгоритма
Способ 1. Вычитанием (исторический, медленный)
Пока числа не равны: из большего вычитаем меньшее.
\[ (48,18)\to(30,18)\to(12,18)\to(12,6)\to(6,6) \] Ответ: 6.
Способ 2. Делением с остатком (основной, быстрый)
Словесная блок-схема:
- Ввести \(a\), \(b\).
- Пока \(b \neq 0\):
- \(r := a \bmod b\);
- \(a := b\);
- \(b := r\).
- Вывести \(a\).
Важно: присваивания идут одновременно (сначала вычисляем \(r\), а потом сдвигаем пару), иначе потеряем значение.
4. Пример с проверкой: \(\text{НОД}(48,18)\)
| Шаг | \(a\) | \(b\) | \(a \bmod b\) |
|---|---|---|---|
| 1 | 48 | 18 | 12 |
| 2 | 18 | 12 | 6 |
| 3 | 12 | 6 | 0 |
Как только остаток стал 0, работаем с парой \((12, 6)\), и ответ — это \(b = 6\).
Проверка: \(48 = 6\cdot8\), \(18=6\cdot3\), а 8 и 3 взаимно просты — значит 6 действительно наибольший. ✔
5. Программа (Python)
def nod(a, b):
while b != 0:
a, b = b, a % b # одна строка — одновременное присваивание
return a
print(nod(48, 18)) # 6
Рекурсивный вариант — короче, но по сути тот же:
def nod(a, b):
return a if b == 0 else nod(b, a % b)
Если числа могут быть отрицательными или одно из них 0 — берём модули и помним: \(\text{НОД}(a,0)=|a|\).
Трассировка для самопроверки: \(48,18 \to 18,12 \to 12,6 \to 6,0\) — три прохода цикла.
6. Свойства и оценка
- Число шагов очень маленькое: на каждом шаге остаток хотя бы вдвое меньше предыдущего, поэтому шагов порядка \(\log_2(\min(a,b))\) — для чисел до миллиарда это меньше 50 шагов.
- \(\text{НОД}(a,b)=\text{НОД}(b,a)\) — порядок чисел не важен.
- Если \(\text{НОД}(a,b)=1\), числа называют взаимно простыми.
7. Где применяется
- Сокращение дробей: \(\frac{48}{18}\): делим оба числа на 6 → \(\frac{8}{3}\).
- НОК через НОД: \[ \text{НОК}(a,b)=\frac{a\cdot b}{\text{НОД}(a,b)} \]
- Решение линейных уравнений вида \(ax+by=1\) (расширенный алгоритм Евклида).
- Криптография (RSA), где нужны взаимно простые числа.
8. Типичные ошибки
- Перепутать порядок присваивания: сначала \(a:=b\), потом \(r:=a \bmod b\) — уже неверно, старое \(a\) потеряно.
- Остановиться, когда остаток ещё не 0, и выдать \(r\) вместо \(b\).
- Считать, что алгоритм ищет все делители — он находит только наибольший общий.
Теперь ты можешь проверить себя: прогони \((1071, 462)\) — должно получиться 21 за 3 шага.