Алгоритм Евклида — это классический метод для нахождения наибольшего общего делителя (НОД) двух целых чисел. Он был описан древнегреческим математиком Евклидом в его труде "Начала" более двух тысяч лет назад и до сих пор широко используется.
Суть алгоритма
Основная идея алгоритма Евклида заключается в следующем: наибольший общий делитель двух чисел не изменяется, если большее число заменить остатком от деления на меньшее. То есть:
gcd(a,b)=gcd(b,amodb)
где a≥b, а \mod означает остаток от деления.
Пошаговое описание
Пусть даны два числа a и b, где a≥b:
- Делим a на b, находим остаток r=amodb.
- Если r=0, то gcd(a,b)=b.
- Если r=0, заменяем a на b, а b на r, и повторяем шаг 1.
Пример
Найдем gcd(48,18):
- 48mod18=12 → gcd(48,18)=gcd(18,12)
- 18mod12=6 → gcd(18,12)=gcd(12,6)
- 12mod6=0 → gcd(12,6)=6
Ответ: gcd(48,18)=6
Преимущества
Алгоритм Евклида работает быстро, даже для больших чисел. Он легко реализуется и используется в различных разделах математики, включая теорию чисел и криптографию.
Расширенный алгоритм Евклида
Существует также расширенная версия алгоритма, которая не только находит НОД, но и вычисляет такие целые числа x и y, что:
ax+by=gcd(a,b)
Этот результат используется, например, для нахождения обратного элемента по модулю.