Евклида алгоритм, способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме в «Началах» Евклида. Для случая положительных чисел а и b, причём a³ b, этот способ состоит в следующем. Деление с остатком числа а на число b всегда приводит к результату а = nb + b₁, где частное n — целое положительное число, а остаток b₁— либо 0, либо положительное число, меньшее b (0 £b₁< b). Будем производить последовательное деление:

где все n_i — положительные целые числа и 0 £b₁ < b_i-1 до тех пор, пока не получится остаток, равный нулю. Этот последний остаток b_k+1 можно не писать, так что ряд равенств (*) закончится так: b_k-2 = n_k-1 + b_k, b_k-1 = n_kb_k.

Последний положительный остаток b_к в этом процессе и является наибольшим общим делителем чисел а и b. Евклида алгоритм служит не только для нахождения наибольшего общего делителя, но и для доказательства его существования. В случае многочленов или отрезков поступают сходным образом. В случае несоизмеримых отрезков (см. Соизмеримые и несоизмеримые величины) Евклида алгоритм оказывается бесконечным.