БОЛЬШАЯ СОВЕТСКАЯ ЭНЦИКЛОПЕДИЯ, БСЭ БОЛЬШАЯ СОВЕТСКАЯ ЭНЦИКЛОПЕДИЯ, БСЭ
Навигация:

Библиотека DJVU
Photogallery

БСЭ

Статистика:


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

Значение слова "Евклида алгоритм" в Большой Советской Энциклопедии


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

В Большой Советской Энциклопедии рядом со словом "Евклида алгоритм"

Евклид | Буква "Е" | В начало | Буквосочетание "ЕВ" |


Статья про слово "Евклида алгоритм" в Большой Советской Энциклопедии была прочитана 3224 раз


Интересное