ЕВКЛИДА АЛГОРИТМ
способ
нахождения наибольшего общего делителя двух целых чисел, двух многочленов
или общей меры двух отрезков. Описан в геометрич. форме в "Началах" Евклида.
Для
случая положит. чисел а и Ь, причём
этот способ состоит в следующем. Деление с остатком числа а на
число Ъ всегда приводит к результату
где частное
- целое положит.
число, а остаток
- либо 0,
либо положит. число, меньшее
Будем производить последоват. деление:
где все
-
положит. целые числа и
до тех
пор, пока не получится остаток, равный нулю. Этот последний остаток
можно не писать, так что ряд равенств (*) закончится так:
Последний положит. остаток
в этом процессе и является наибольшим общим делителем чисел а и
b.
Е.
а. служит не только для нахождения наибольшего общего делителя, но и для
доказательства его существования. В случае многочленов или отрезков поступают
сходным образом. В случае несоизмеримых отрезков (см. Соизмеримые и
несоизмеримые величины) Е. а. оказывается бесконечным.
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я