logo search
atch_exam_1-8

8) Нод многочленов. Алгоритм Евклида.

Наибольший общий делитель двух многочленов  Наибольший общий делитель многочленов f(x) и g(x) - такой их общий делитель d(x), который делится на любой другой их общий делитель.

Алгоритм Евклида для целых чисел

Пусть a и b — целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое rk — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

a = bq0 + r1

b = r1q1 + r2

r1 = r2q2 + r3

rk − 2 = rk − 1qk − 1 + rk

rn − 1 = rnqn

Тогда НОД(a,b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности.

Существование таких r1,r2,..., то есть возможность деления с остатком m на n для любого целого m и целого  , доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений:

Пусть a = bq + r, тогда НОД (a, b) = НОД (b, r).