Question

Используя алгоритм Евклида, найдите наибольший общий делитель чисел:
437 и 133
735 и 1050
1848 и 375
805 и 1265

Answer 1

Продемонстрируем на третьем примере
1848      375

Находим разность:
1848-375=1473

Теперь получили числа:
1473        375

Находим разность
1473-375=1098 и т.д:

1098-375=723

723-375=348

375-348=27
(ВНИМАНИЕ! Всегда от большего вычитаем меньшее - то есть нельзя вычитать 348-375 !)
348-27=321
321-27=294
294-27=267
267-27=240
240-27=213
213-27=186
186-27=159
159-27=132
132-27=105
105-27=78
78-27=51
51-27=24
27-24=3
24-3=21
21-3=18
18-3=15
15-3=12
12-3=9
9-3=6
6-3=3

Итак НОД=3
1848/3=616
375/3=125

Как видим, алгоритм Евклида довольно медленный.
Позже получили расширенный алгоритм Евклида, где монотонное вычитание заменили делением. Вычисление НОД расширенным алгоритмом значительно быстрее