Алгоритм Евклида
Алгоритм Евклида позволяет быстро найти [[greatest-common-divisor:наибольший общий делитель]] двух натуральных чисел без разложения их на простые множители. Для этого большее число последовательно делят на меньшее, затем делитель заменяют остатком и повторяют действия до получения нулевого остатка.
Что нужно знать перед применением алгоритма
Алгоритм основан на [[division-algorithm:алгоритме деления с остатком]]. Если натуральное число \(a\) делят на натуральное число \(b\), где \(a\ge b\), то существуют единственные целые числа \(q\) и \(r\), такие что выполняется равенство \(a=bq+r\), причём \(0\le r<b\). Число \(q\) называют неполным частным, а \(r\) — [[remainder-of-division:остатком при делении]].
Наибольший общий делитель, или НОД, двух целых чисел — наибольшее натуральное число, на которое делятся оба числа без остатка. Обозначение: \(\operatorname{НОД}(a,b)\) или \((a,b)\).
Если \(a=bq+r\), то \(\operatorname{НОД}(a,b)=\operatorname{НОД}(b,r)\). Иными словами, НОД делимого и делителя не изменится, если вместо делимого взять остаток от деления.
Почему это верно? Любой общий делитель чисел \(a\) и \(b\) делит разность \(a-bq=r\). Значит, он является общим делителем \(b\) и \(r\). Обратно, любой общий делитель \(b\) и \(r\) делит число \(bq+r=a\). Поэтому множества общих делителей совпадают, а значит, совпадают и их наибольшие элементы.
Если числа записаны в неправильном порядке, сначала поставьте большее число на первое место. Например, для пары \(18\) и \(48\) начинайте с деления \(48\) на \(18\).
Пошаговый алгоритм
Для нахождения НОД чисел \(a\) и \(b\), где \(a\ge b>0\), выполните следующие действия.
- Разделите \(a\) на \(b\) с остатком: \(a=bq_1+r_1\).
- Если \(r_1=0\), то НОД равен \(b\) — последнему ненулевому делителю.
- Если \(r_1\ne0\), разделите прежний делитель \(b\) на остаток \(r_1\): \(b=r_1q_2+r_2\).
- Продолжайте деление: каждый раз делите предыдущий делитель на предыдущий остаток.
- Остановитесь, когда получите остаток \(0\). Последний ненулевой остаток и есть НОД.
Остатки при последовательном делении строго убывают: \(b>r_1>r_2>\ldots\ge0\). Поэтому процесс обязательно завершится. Если на первом шаге остаток уже равен нулю, второй шаг не нужен.
Вычислено: \(84=30\cdot2+24\), \(30=24\cdot1+6\), \(24=6\cdot4+0\). Чему равен НОД чисел \(84\) и \(30\)?
Разобранный пример
Найдём \(\operatorname{НОД}(252,198)\) последовательным делением с остатком.
Проверка: \(252=18\cdot14\) и \(198=18\cdot11\), поэтому \(18\) действительно делит оба числа. Полученный результат можно использовать, например, при сокращении дроби или при решении задач на делимость.
В цепочке делений ответом является последний ненулевой остаток, а не последний делитель в произвольной строке и не первое полученное частное.
Как оформлять решение на экзамене
В письменном решении удобно записывать все равенства одно под другим. Частные можно указывать, но главное — правильно указать остатки и не пропустить переход к следующей строке.
- Сначала выбраны большее и меньшее числа.
- В каждой строке делится предыдущий делитель на предыдущий остаток.
- Каждый остаток меньше делителя и неотрицателен.
- Процесс остановлен после остатка \(0\).
- Ответом назван последний ненулевой остаток.
В задачах на выражения алгоритм Евклида может применяться к числам, полученным после вычислений. Сначала аккуратно упростите выражение, затем найдите НОД. Если требуется сократить дробь, разделите числитель и знаменатель на найденный НОД; связь с другими действиями над делителями рассматривается на странице [[gcd-lcm-product:связь НОД и НОК двух чисел]].
Если \(a=bq+r\), то можно многократно заменять пару чисел \((a,b)\) на \((b,r)\), пока остаток не станет нулевым. Это и есть алгоритм Евклида; его результат не зависит от выбранных частных, если деление выполнено правильно.
Связь с другими способами нахождения НОД
НОД можно находить также по [[gcd-by-factorization:разложениям на простые множители]]: выписать общие простые множители в наименьших степенях и перемножить их. Для небольших чисел этот способ часто удобен, но при больших числах разложение может быть длинным. Алгоритм Евклида обычно быстрее и не требует искать простые множители.
После нахождения НОД полезно помнить [[gcd-lcm-product:связь НОД и НОК двух чисел]]: произведение НОД и НОК двух натуральных чисел равно произведению самих чисел. При работе с разложениями помогают также [[canonical-factorization:каноническое разложение числа]] и свойства [[remainder-properties:остатка при делении]].
1. Делят каждый раз исходные числа, а не предыдущий делитель на предыдущий остаток. 2. Останавливаются на первом ненулевом остатке. 3. Путают частное и остаток. 4. Записывают остаток, равный или больший делителя — это нарушает условие \(0\le r<b\). 5. При нулевом первом остатке продолжают деление на ноль. 6. В ответе указывают последний делитель вместо последнего ненулевого остатка.
Быстрая проверка понимания
Quick-test
Главное
- Алгоритм Евклида находит НОД через последовательные деления с остатком.
- При равенстве \(a=bq+r\) можно заменить пару \((a,b)\) на \((b,r)\), не изменяя НОД.
- Делитель каждой новой строки — предыдущий остаток.
- Алгоритм заканчивается после получения нулевого остатка.
- Ответ — последний ненулевой остаток.