Алгоритм Евклида работает так: 2

1. На каждом этапе производится деление большего из пары двух чисел на меньшее. 4
2. Остаток записывается и используется при дальнейших вычислениях в качестве нового делителя для предыдущего. 4
3. Вычисление остатка производят до тех пор, пока он не будет равен нулю. 4
4. Тогда последний использованный делитель и будет являться наибольшим общим делителем, полученным через алгоритм Евклида. 4

В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и остатка от деления большего числа на меньшее. 1 Процесс повторяется, пока числа не станут равными. 1