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

чисел. Это помогает сокращать дроби с достаточно большими числителями и знаменателями.

и b. Очевидно, что в случае, когда а = b, общей мерой служит любой из данных отрезков. Но допус­тим, а > b. Тогда можно отложить от­резок b на отрезке а максимальное число раз.
Если отрезок а исчерпается целым количеством отрезков b, то отрезок b и будет их наибольшей общей мерой. Вполне вероятно, однако, что отрезок b не уложится на отрезке а целое число раз и останется небольшой «кусочек» r1. Естественно теперь и его испытать в качестве общей меры отрезков а и b. Он подойдёт на эту роль, если целое число раз уместится на отрезке b. Если же при этом опять получим остаток r2, то на следующем шаге будем испытывать отрезок r2, но уже по отношению к отрезку r1
Если в конце кон­цов получится такой отрезок rk, который целое число раз отложится в предыдущем остатке rk-1; то он и будет общей мерой всех отрезков. Если же этот процесс никогда не закончится, то об­щей меры у отрезков а и Ь не существует — они несоизм.