Памятка нахождения НОД "Алгоритм Евклида"

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

Древние греки придумали замечательный способ, позволяющий искать наибольший общий делитель двух натуральных чисел без разложения на множители. Он носил название «Алгоритма Евклида». О жизни греческого математика Евклида достоверные данные неизвестны. Ему принадлежит выдающееся научное произведение, называемое «Начала». Оно состоит из 13 книг и излагает основы всей древнегреческой математики. Именно здесь описывается алгоритм Евклида, который заключается в том, что наибольшим общим делителем двух натуральных чисел является последний, отличный от нуля, остаток при последовательном делении этих чисел. Под последовательным делением подразумевается деление большего числа на меньшее, меньшего числа на первый остаток, первого остатка на второй остаток, и т.д., пока деление не закончится без остатка. Положим, требуется найти НОД(455; 312), тогда

455:312=1(ост.143), получаем 455=3121+143,

312:143=2(ост.26), получаем 312=143+26,

143:26=5(ост.13), получаем 143=25+13,

26:13=2(ост.0), получаем 26=13 Последний делитель или последний, отличный от нуля остаток 13 и будет искомым НОД(455; 312)=13

Задание: найти наибольший общий делитель двух натуральных чисел без разложения на множители

1) 675 и 825

2) 7920 и 594