НОВОСТИ    БИБЛИОТЕКА    ЭНЦИКЛОПЕДИЯ    БИОГРАФИИ    КАРТА САЙТА    ССЫЛКИ    О ПРОЕКТЕ  

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

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

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

(*)

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

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

Е. а. для многочленов или отрезков аналогичны Е. а. для целых чисел. В случае несоизмеримых отрезков применение Е. а. приводит к бесконечному процессу.

БСЭ-З.


Источники:

  1. Математическая энциклопедия: Гл. ред. И. М. Виноградов, т. 2 Д - Коо.-М.: «Советская Энциклопедия», 1979.-1104 стб., ил.








© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2019
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'Математическая библиотека'
Рейтинг@Mail.ru