Эта тема о том, как быстро найти наибольший общий делитель больших чисел: он нужен, например, чтобы сокращать дроби. Сначала вспомним определение.
Наибольший общий делитель натуральных чисел a и b — наибольшее из чисел, на которые делятся и a, и b; его обозначают НОД(a; b). Договариваются, что НОД(a; 0) = a: число 0 делится на любое натуральное число.
Искать НОД через разложение на простые множители для больших чисел трудно: нужно делить на многие простые числа. Есть способ проще — алгоритм Евклида. Он основан на теореме:
Если a = bc + r, то НОД(a; b) = НОД(b; r).
Действительно, если d делит a и b, то d делит и r = a - bc; а если d делит b и r, то d делит и a = bc + r. Общие делители у пар (a; b) и (b; r) одни и те же — значит, и наибольший общий.
Алгоритм: делим a на b с остатком, потом делитель — на остаток, потом прежний остаток — на новый, и так далее. Остатки уменьшаются и когда-нибудь станут равны нулю. НОД равен последнему ненулевому остатку.
Пример. НОД(119 597; 52 029):
119 597 = 52 029 · 2 + 15 539
52 029 = 15 539 · 3 + 5412
15 539 = 5412 · 2 + 4715
5412 = 4715 · 1 + 697
4715 = 697 · 6 + 533
697 = 533 · 1 + 164
533 = 164 · 3 + 41
164 = 41 · 4 + 0
Последний ненулевой остаток — 41, значит, НОД(119 597; 52 029) = 41.
Сократить дробь до несократимой — значит разделить числитель и знаменатель на их НОД.