Большая Советская энциклопедия II

ЕВКЛИДА АЛГОРИТМ

способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме в «Началах» Евклида. Для случая положительных чиселаиb,причёмa≥b,этот способ состоит в следующем. Деление с остатком числаана числоbвсегда приводит к результатуа=nb+b1,где частноеn —целое положительное число, а остатокb1—либо 0, либо положительное число, меньшееb(0 ≤b1< b). Будем производить последовательное деление:
где всеni—положительные целые числа и 0 ≤b1<bi-1до тех пор, пока не получится остаток, равный нулю. Этот последний остатокbk+1можно не писать, так что ряд равенств (*) закончится так:
bk-2=nk-1+bk,
bk-1= nkbk.
Последний положительный остатокbкв этом процессе и является наибольшим общим делителем чиселаиb.Е. а. служит не только для нахождения наибольшего общего делителя, но и для доказательства его существования. В случае многочленов или отрезков поступают сходным образом. В случае несоизмеримых отрезков (см. Соизмеримые и несоизмеримые величины) Е. а. оказывается бесконечным.

  1. евклида алгоритм—ЕВКЛИДА АЛГОРИТМ способ нахождения наибольшего общего делителя двух целых чисел двух многочленов или общей меры двух отрезков. Описан в геометрич. форме в Началах Евклида...Большая советская энциклопедия
  2. евклида алгоритм—ЕВКЛИДА АЛГОРИТМ способ нахождения наибольшего общего делителя двух целых чисел двух многочленов или общей меры двух отрезков. Описан в геометрич. форме в Началах Евклида...Большая советская энциклопедия
  3. евклида алгоритм—ЕВКЛИДА АЛГОРИТМ способ нахождения наибольшего общего делителя двух целых чисел двух многочленов или общей меры двух отрезков. Описан в геометрической форме Евклидом....Большой энциклопедический словарь III
  4. евклида алгоритм—ЕВКЛИДА АЛГОРИТМ способ нахождения наибольшего общего делителя двух целых чисел двух многочленов или общей меры двух отрезков. Описан в геометрической форме Евклидом....Большой Энциклопедический словарь V
  5. евклида алгоритм—способ нахождения наиб. общего делителя двух целых чисел двух многочленов или общей меры двух отрезков. Описан в геом. форме Евклидом....Естествознание. Энциклопедический словарь
  6. евклида алгоритм—способ нахождения наибольшего общего делителя двух целых чисел двух многочленов и вообще двух элементов евклидова кольцаi или общей меры двух отрезков. Описан в геометрич...Математическая энциклопедия
  7. евклида алгоритм—Эклда алгарытм...Русско-белорусский математический словарь
  8. евклида алгоритм—ЕВКЛИДА АЛГОРИТМ способ нахождения наибольшего общего делителя двух целых чисел двух многочленов или общей меры двух отрезков. Описан в геометрической форме Евклидом....Современный энциклопедический словарь
  9. евклида алгоритм—ЕВКЛИДА АЛГОРИТМ способ нахождения наибольшего общего делителя двух целых чисел двух многочленов или общей меры двух отрезков. Описан в геометрической форме Евклидом....Энциклопедический словарь естествознания