Евкліда алгоритм, спосіб знаходження найбільшого загального дільника двох цілих чисел, двох многочленів або загальної міри двох відрізань. Описаний в геометричній формі в «Початках» Евкліда . Для випадку позитивних чисел а і b, причому а ³ b, цей спосіб полягає в наступному. Ділення із залишком числа а на число b завжди приводить до результату а = nb + b 1 , де приватне n — ціле позитивне число, а залишок b 1 — або 0, або позитивне число, менше b (0 £ b 1 < b ) . вироблятимемо послідовне ділення:
де все n i — позитивні цілі числа і 0 £ b 1 < b i-1 до тих пір, поки не вийде залишок, рівний нулю. Цей останній залишок b k+1 можна не писати, так що ряд рівності (*) закінчиться так:
b k-2 = n k-1 + b до ,
b k-1 = n до b до .
Останній позитивний залишок b до в цьому процесі і є найбільшим загальним дільником чисел а і b. Е. а. служить не лише для знаходження найбільшого загального дільника, але і для доказу його існування. В разі многочленів або відрізань поступають схожим чином. В разі несумірних відрізань (див. Сумірні і несумірні величини ) Е. а. виявляється безконечним.
