Математическая энциклопедия

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

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

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

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

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

БСЭ-3.


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