Свой известный алгоритм Евклид придумал для решения задачи о соизмеримости двух отрезков. Общей мерой отрезков с длинами L1 и L2 называется отрезок с наибольшей возможной длиной L, который можно уложить без остатка как в первом отрезке, так и во втором. Как известно, алгоритм заключается в следующем. Меньший отрезок (длины L2) укладывается в большем (длины L1) максимально возможное число, скажем a1, раз, после чего остается отрезок длины L1 − a1L2, который обозначим L3. Затем повторяем эту операцию с L2 и L3 и т. д. Работу алгоритм заканчивает на том шаге, скажем с номером k, когда полученный на предыдущем шаге отрезок Lk+1 ...