Гайди НОД чисел 4455 и 4725

НОД(4455; 4725) = 135.

Решаем алгоритмом Евклида: большее число делим на меньшее с остатком, затем меньшее — на остаток, и так до нуля. Последний ненулевой остаток и есть НОД.

\[ 4725 = 4455 \cdot 1 + 270 \]

\[ 4455 = 270 \cdot 16 + 135 \]

\[ 270 = 135 \cdot 2 + 0 \]

Последний ненулевой остаток — 135.

Проверка:

\[ 4455 : 135 = 33 \]

\[ 4725 : 135 = 35 \]

Оба числа делятся на 135, и после сокращения получаются взаимно простые числа 33 и 35, значит, 135 — наибольший общий делитель.

Принцип: на каждом шаге замена пары чисел \((a,b)\) на \((b, \text{остаток от } a : b)\) не меняет их общий наибольший делитель, а числа уменьшаются. Когда в остатке получается 0, делитель на предыдущем шаге — и есть НОД.