Принцип работы алгоритма Евклида заключается в последовательном делении большего числа на меньшее, потом меньшего на остаток от предыдущего деления и так далее до тех пор, пока одно число не поделится на другое. 2
Последний отличный от нуля остаток и будет искомым наибольшим общим делителем (НОД) исходных чисел. 2
Алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и остатка от деления большего числа на меньшее. 5