Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



Разделить целое число a на число b с остатком – это значит найти такие числа q и r c 0 £ r < | b |, при которых выполняется равенство

a = q · b + r.

Разделить многочлен f на многочлен g с остатком – это значит найти такие многочлены q и r c 0 £ deg r < deg g, при которых выполняется равенство

f = q · g + r.

Для вычисления НОД(r 0 = a, r 1 = b) производится деление с остатком по следующей схеме:

a = r 0 = q 1 r 1 + r 2,

b = r 1 = q 2 r 2 + r 3,

.....

rm -2 = qm -1 bm -1 + rm,

rm -1 = qmrm.

Работа алгоритма Евклида основана на том, что отображение сохраняет наибольший общий делитель.

Отображение работает до a = НОД, b = 0.





Дата публикования: 2014-11-02; Прочитано: 374 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с)...