"Информатика", Семакин И.Г., Залогова Л.А., Русаков С.В., Шестакова Л.В.
Алгоритм Евклида помогает быстро находить наибольший общий делитель двух чисел с помощью деления с остатком. На каждом шаге большую величину заменяют остатком, а меньшую переносят на её место: НОД при этом не меняется. Остатки становятся всё меньше, поэтому вычисления заканчиваются. Ответом служит последний ненулевой остаток; если он равен 1, числа взаимно просты.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Наибольший общий делитель (НОД) — самое большое натуральное число, на которое делятся без остатка два или несколько чисел. Например, общие делители 12 и 18 — 1, 2, 3 и 6, поэтому их НОД равен 6. НОД нужен, чтобы находить общую меру чисел, в частности сокращать дроби.
Остаток от деления — число, которое получается при делении с остатком и меньше делителя. Запись a = bq + r означает, что a — делимое, b — делитель, q — частное, а r — остаток; при этом 0 ≤ r < b. Остаток показывает, сколько единиц не удалось распределить поровну на группы размера b.
Алгоритм Евклида — последовательность делений с остатком для нахождения НОД двух чисел. После каждого деления вместо исходной пары берут делитель и полученный остаток. Такой способ позволяет не выписывать все делители чисел и постепенно уменьшает вычисления.
Взаимно простые числа — числа, НОД которых равен 1. Это не означает, что сами числа обязательно простые: например, 8 и 15 взаимно просты, хотя оба составные. Понятие помогает понять, можно ли дальше сокращать дробь, составленную из этих чисел.
Пусть a ≥ b и при делении a на b получается остаток r: a = bq + r. Если некоторое число делит и a, и b, то оно делит их разность a − bq, то есть r. Значит, каждый общий делитель исходной пары подходит и для пары (b, r). Обратное тоже верно: общий делитель b и r делит сумму bq + r = a, поэтому набор общих делителей не меняется.
После деления мы рассматриваем уже не большие исходные числа, а пару (b, r). Затем делим b на r и снова заменяем пару делителем и остатком. Причина, по которой можно повторять эти действия, — на каждом шаге НОД сохраняется. В итоге вычисления сводятся к короткой цепочке, в которой числа обычно быстро уменьшаются.
Остаток всегда неотрицателен и меньше делителя. Поэтому каждый следующий ненулевой остаток меньше предыдущего делителя, а значит, остатки образуют убывающую последовательность целых чисел. Такая последовательность не может продолжаться бесконечно: рано или поздно остаток станет нулём.
Когда остаток равен нулю, деление было точным: текущий делитель делит число, которое делили. Этот делитель и есть последний ненулевой остаток. Поскольку на предыдущих шагах НОД не менялся, он равен НОД первоначальных чисел; сам ноль общим делителем считать ответом нельзя.
Вручную алгоритм удобно записывать строками: деление, остаток и новая пара чисел. В программе те же действия повторяют в цикле: вычисляют остаток r, затем присваивают a значение b, а b — значение r. Цикл работает, пока b не равно нулю; после его завершения в a находится НОД.
| Этап | Действие | Что получают | Условие перехода |
|---|---|---|---|
| Выбор чисел | Расположить числа так, чтобы первое не было меньше второго | Пара чисел a и b | a ≥ b |
| Деление с остатком | Разделить a на b | Остаток r: a = bq + r | r = 0 или r > 0 |
| Замена пары | Заменить пару (a, b) на (b, r) | Новая пара для следующего шага | Продолжать, если r ≠ 0 |
| Остановка | Прекратить деления при нулевом остатке | Последний ненулевой остаток | Последний ненулевой остаток является НОД |
Читайте таблицу сверху вниз: после деления решите, равен ли остаток нулю. Если нет, запишите новую пару и повторите деление; если да, остановитесь. Ответом будет делитель последнего деления, а не нулевой остаток.
Задача 1. Найти НОД чисел 48 и 18. Начинаем с большего числа, чтобы деление сразу дало остаток меньше делителя. После первого деления новая пара — делитель и полученный остаток. Во втором делении остаток становится нулевым, поэтому последний ненулевой остаток и будет ответом.
Ответ: НОД(48, 18) = 6. Число 6 — последний ненулевой остаток, и оно делит оба исходных числа.
Задача 2. Найти НОД чисел 252 и 105 и определить, взаимно ли они просты. Продолжаем деления, каждый раз заменяя пару на делитель и остаток. Когда остаток обнулится, сравним предыдущий остаток с единицей. Только при НОД, равном 1, числа взаимно просты.
Ответ: НОД(252, 105) = 21. Числа не являются взаимно простыми, поскольку их НОД не равен 1.
Задача 3. Найти НОД чисел 1071 и 462, записав шаги и программу с циклом. Сначала выполним деления вручную, чтобы увидеть, какие действия программа будет повторять. Для программного варианта нужны две переменные a и b и временная переменная r: она сохраняет остаток до замены чисел. Цикл заканчивается, когда b становится нулём.
Алгоритм программы: a := 1071; b := 462; пока b ≠ 0: r := a mod b; a := b; b := r; вывести a. Операция mod даёт остаток от деления, а присваивания готовят пару для следующего повторения цикла. Ответ: НОД(1071, 462) = 21.
Путают делимое и делитель. При записи a = bq + r делимое — a, а делитель — b; остаток должен быть меньше b. Путаница меняет цепочку вычислений и может привести к неверному ответу. Проверьте каждую строку умножением делителя на частное с добавлением остатка.
Останавливаются на первом остатке. Первый остаток только начинает новую пару и обычно ещё не является НОД. Ошибку допускают, если воспринимают первое деление как завершённое решение. Продолжайте, пока не получите нулевой остаток.
Забывают заменить пару чисел. После деления a на b следующая пара — (b, r), а не исходные числа и не (a, r). Иначе следующий шаг алгоритма выполняется не для тех величин. Перед каждым новым делением явно записывайте делитель и предыдущий остаток.
Принимают ноль за НОД. Нулевой остаток сообщает, что деление на предыдущем шаге было точным, но сам ответ — делитель этого деления. Путаница возникает из-за остановки именно на нуле. Найдите последний ненулевой остаток и проверьте, делит ли он оба исходных числа.
Для работы алгоритма нужны деление с остатком, понятие делимости и знание общего делителя. Если эти понятия знакомы, можно понять, почему остаток меньше делителя и как проверять полученный ответ. Алгоритм Евклида пригодится при сокращении дробей: числитель и знаменатель делят на их НОД, чтобы получить несократимую дробь. Его повторяющиеся действия также служат примером циклического алгоритма и программы для обработки целых чисел.
Почему НОД не изменяется после замены большего числа остатком?
Пусть a = bq + r. Если число делит a и b, оно делит и разность r = a − bq. И наоборот: общий делитель b и r делит a = bq + r. Значит, общие делители пары (a, b) и пары (b, r) совпадают.
Почему алгоритм Евклида всегда заканчивается?
Каждый новый остаток — целое неотрицательное число, меньшее предыдущего делителя. Поэтому ненулевые остатки строго убывают, а бесконечно убывать среди целых чисел они не могут. В конце получается нулевой остаток.
Какой остаток считать ответом: нулевой или предыдущий?
Ответ — последний ненулевой остаток. Нулевой остаток означает, что предыдущий делитель делится нацело и уже является НОД.
Можно ли начинать алгоритм с меньшего числа?
Да, но перед первым делением числа удобнее расположить так, чтобы a ≥ b. Если первым делить меньшее число на большее, частное будет нулевым, а остаток — меньшее число; алгоритм просто переставит числа на нужные места.
Как записать алгоритм Евклида с помощью цикла в программе?
Пока b не равно нулю, вычисляют r как остаток от деления a на b, затем присваивают a значение b, а b — значение r. После завершения цикла в a находится НОД. Важно сначала сохранить остаток, иначе значение b будет потеряно.
§ 16. Алгоритм Евклида
