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

способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме в «Началах» Евклида. Для случая положительных чисел а и b, причём a ≥b,этот способ состоит в следующем. Деление с остатком числа а на число b всегда приводит к результату а = nb + b₁,где частное n — целое положительное число, а остаток b₁ — либо 0, либо положительное число, меньшее b(0 ≤ 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. Е. а. служит не только для нахождения наибольшего общего делителя, но и для доказательства его существования. В случае многочленов или отрезков поступают сходным образом. В случае несоизмеримых отрезков (см. Соизмеримые и несоизмеримые величины) Е. а. оказывается бесконечным.

ЕВКЛИДА АЛГОРИТМ - способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме Евклидом.

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

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

* * *

ЕВКЛИ́ДА АЛГОРИ́ТМ, способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме Евклидом.

- способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов (и вообще, двух элементов евклидова, кольца )или общей меры двух отрезков. Описан в геометрич. форме в "Началах" Евклида (3 в. до н. э.).

Для случая положительных целых чисел этот способ состоит в следующем. Деление с остатком числа ана число b всегда приводит к результату a=nb+b₁, где частное п- целое положительное число, а остаток b₁ либо 0, либо положительное число, меньшее b, Производится последовательное деление:

где все n_i - положительные целые числа и до тех пор, пока не получится остаток, равный 0. Ряд равенств (*) закончится так:

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

БСЭ-3.

способ нахождения наиб. общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геом. форме Евклидом.