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

Определение. Алгоритм вычисления НОД: gcd(a,b) = gcd(b, r), где r — остаток от деления a на b; повторять до нулевого остатка. Последний ненулевой остаток — НОД.

В каких главах встречается

• Натуральные числа: от счёта до глубин теории чисел

Связанные концепты

Требуются перед изучением:

• Наибольший общий делитель
• Деление с остатком