"Алгебра (в 3 частях)", Петерсон Л.Г., Абраров Д.Л., Чуткова Е.В.
Алгоритм Евклида — быстрый способ найти наибольший общий делитель двух натуральных чисел с помощью последовательных делений с остатком. На каждом шаге предыдущий делитель делят на полученный ненулевой остаток. Процесс заканчивается, когда остаток становится равным нулю, а НОД исходных чисел равен последнему ненулевому остатку. По результату также легко определить, являются ли числа взаимно простыми.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Наибольший общий делитель (НОД) двух натуральных чисел — наибольшее натуральное число, на которое делятся оба числа. Например, НОД(12, 18) = 6, потому что 6 делит оба числа, а большего общего делителя нет. Это число нужно находить, чтобы работать с делимостью и сокращать дроби.
Остаток от деления — число r в записи a = bq + r, где q — частное, а 0 ≤ r < b. Например, при делении 17 на 5 получаем 17 = 5 · 3 + 2, поэтому остаток равен 2. Такое равенство помогает переходить от больших чисел к меньшим.
Алгоритм Евклида — последовательное деление с остатком, позволяющее найти НОД двух натуральных чисел. После каждого деления в следующем шаге используют предыдущий делитель и остаток. Благодаря этому НОД находится без выписывания всех делителей чисел.
Взаимно простые числа — натуральные числа, НОД которых равен 1. У таких чисел может не быть общих делителей, кроме единицы. Например, числа 8 и 15 взаимно просты.
Пусть при делении a на b получается a = bq + r. Общий делитель чисел a и b делит число bq, потому что является делителем b, а значит, делит и разность a − bq = r. Поэтому любой общий делитель пары (a, b) является общим делителем пары (b, r), и наоборот: из a = bq + r следует, что общий делитель b и r делит a. Значит, НОД(a, b) = НОД(b, r).
Сначала большее число делят на меньшее с остатком. Если остаток не равен нулю, предыдущее меньшее число становится новым делимым, а остаток — новым делителем. Например, после записи 84 = 30 · 2 + 24 следующий шаг имеет вид 30 = 24 · 1 + 6. Так постепенно исходная пара заменяется парами всё меньших чисел.
Процесс обязательно заканчивается, потому что каждый следующий ненулевой остаток меньше предыдущего делителя. Остатки являются неотрицательными целыми числами, а последовательность натуральных чисел не может бесконечно убывать. В некоторый момент деление выполнится без остатка.
НОД сохраняется при каждом переходе от пары (a, b) к паре (b, r). На последнем шаге получается равенство вида b = rq, то есть последний ненулевой остаток делит предыдущее число без остатка. Он также делит все предыдущие числа цепочки, поэтому является общим делителем исходных чисел. Так как НОД на каждом шаге не менялся, этот остаток и есть искомый НОД.
Вычисления удобно записывать цепочкой равенств: a = bq₁ + r₁, b = r₁q₂ + r₂ и так далее. Деления продолжают до равенства rₙ₋₁ = rₙqₙ + 0. Последний остаток, отличный от нуля, записывают в ответ, а если он равен 1, делают вывод о взаимной простоте чисел.
| Шаг | Деление с остатком | Что делать дальше |
|---|---|---|
| Первое деление исходных чисел | Большее число делят на меньшее | Записать частное и остаток |
| Очередное деление предыдущего делителя на ненулевой остаток | Предыдущий делитель делят на предыдущий остаток | Повторять, пока остаток не станет нулём |
| Остановка, когда остаток равен 0 | Последнее деление выполнено без остатка | Не брать нулевой остаток как ответ |
| Определение НОД по последнему ненулевому остатку | Выделить остаток перед нулём | Записать его как НОД исходных чисел |
Таблицу удобно читать сверху вниз: в каждом новом делении используются два числа из предыдущей строки. Следите, чтобы остаток был меньше делителя, иначе деление записано неверно. В последней строке ответом становится не ноль, а последний ненулевой остаток.
Нужно применить алгоритм к числам 18 и 12. Сначала делим большее число на меньшее и получаем ненулевой остаток. После этого проверяем, делится ли предыдущий делитель на найденный остаток.
Ответ: НОД(18, 12) = 6. Остаток 6 подходит, потому что он делит и 18, и 12.
Одного деления здесь недостаточно, поэтому важно не остановиться на первом остатке. После каждой записи меняем пару чисел: берём прежний делитель и полученный остаток. Дойдём до нулевого остатка, чтобы выбрать правильный ответ.
Ответ: НОД(84, 30) = 6. Первый остаток 24 не является ответом, поскольку его нужно было использовать в следующем делении.
Сначала найдём НОД, а затем сравним его с единицей. Если последний ненулевой остаток окажется равным 1, числа будут взаимно простыми. Все деления проверяем по правилу: делимое равно произведению делителя и частного плюс остаток.
Ответ: НОД(252, 198) = 18. Числа не являются взаимно простыми, потому что их НОД не равен 1.
Остановка после первого деления. Иногда первый остаток принимают за НОД, хотя цепочка ещё не закончена. Такая ошибка возникает из-за невнимательности к правилу перехода. Проверьте, делится ли предыдущий делитель на остаток без остатка.
Неверный выбор чисел для следующего шага. Нельзя снова делить исходные числа или менять местами остаток и неподходящее число. Причина ошибки — запоминание отдельных действий без схемы перехода. Запишите рядом: новый делитель — остаток, новое делимое — прежний делитель.
Ответом считают ноль. Нулевой остаток показывает, что предыдущее число делится нацело, но НОД равен числу перед нулём. Ошибку легко заметить, если проверить, делит ли названный ответ исходные числа. Ноль не является натуральным общим делителем в этой задаче.
Путают частное и остаток. При записи a = bq + r частное q показывает, сколько раз делитель помещается в делимом, а r — что осталось. Остаток должен быть неотрицательным и меньше делителя. Для проверки перемножьте делитель и частное и прибавьте остаток.
До изучения алгоритма Евклида нужно уметь делить с остатком и понимать смысл делителя числа. Без этого трудно правильно составить равенство a = bq + r и выбрать следующий шаг. Эти навыки являются основой всей цепочки вычислений.
Алгоритм пригодится при сокращении дробей: сначала находят НОД числителя и знаменателя, а затем делят на него оба числа. Он также помогает решать задачи на делимость, когда нужно быстро установить общий делитель больших чисел. Поэтому алгоритм заменяет длинный перебор делителей.
Понятия НОД и взаимно простых чисел встречаются при изучении дробей и свойств натуральных чисел. НОД показывает, какие множители можно вынести или сократить. Проверка НОД на равенство 1 позволяет распознать взаимно простые числа.
Почему при переходе к остатку НОД не меняется?
Если a = bq + r, то r = a − bq. Любой общий делитель чисел a и b делит и число r, поэтому общие делители пар (a, b) и (b, r) совпадают.
Как понять, какие числа делить на очередном шаге?
Сначала большее число делят на меньшее. Затем предыдущий делитель становится делимым, а остаток — новым делителем: делят b на r.
Почему алгоритм Евклида обязательно заканчивается?
Каждый новый ненулевой остаток меньше предыдущего. Натуральные числа не могут уменьшаться бесконечно, поэтому через несколько шагов появится нулевой остаток.
Какой остаток считать ответом?
Нулевой остаток ответом не является. НОД равен последнему ненулевому остатку, то есть остатку непосредственно перед первым нулевым.
Как по алгоритму определить, что числа взаимно простые?
Нужно выполнить алгоритм Евклида и найти последний ненулевой остаток. Если он равен 1, исходные числа взаимно простые.
2.1.4. Алгоритм Евклида
