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

Евклида алгоритм
        способ нахождения наибольшего общего делителя двух целых чисел, двух многочленов или общей меры двух отрезков. Описан в геометрической форме в «Началах» Евклида. Для случая положительных чисел а и 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. Е. а. служит не только для нахождения наибольшего общего делителя, но и для доказательства его существования. В случае многочленов или отрезков поступают сходным образом. В случае несоизмеримых отрезков (см. Соизмеримые и несоизмеримые величины) Е. а. оказывается бесконечным.

Большая советская энциклопедия. — М.: Советская энциклопедия. 1969—1978.

Смотреть что такое "Евклида алгоритм" в других словарях:

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

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

  • Евклида алгоритм — Алгоритм Евклида  алгоритм для нахождения наибольшего общего делителя двух целых чисел или наибольшей общей меры двух однородных величин. Содержание 1 История 2 Алгоритм Евклида для целых чисел …   Википедия

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

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

  • Алгоритм Евклида — Имеется викиучебник по теме « …   Википедия

  • Алгоритм — У этого термина существуют и другие значения, см. Алгоритм (значения). Для улучшения этой статьи желательно?: Переработать оформление в соответствии с правил …   Википедия

  • Алгоритм Шенкса — (англ. Baby step giant step; также называемый алгоритм больших и малых шагов)  в теории групп, детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный… …   Википедия

  • Алгоритм Фюрера — (англ. Fürer’s algorithm)  быстрый метод умножения больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером[1] из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его… …   Википедия

  • Алгоритм Монтгомери — Алгоритм Монтгомери  приём, позволяющий ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведение числа в степень по модулю, когда модуль велик (порядка сотен бит). Был предложен в 1985 году Питером… …   Википедия

Книги

Другие книги по запросу «Евклида алгоритм» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»