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

Алгебра многочленов над конечным полем.

Часть 1. Теория:

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

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

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

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

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

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

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

Алгебраи́ческое расшире́ние — расширение поля , где каждый элемент алгебраичен над , то есть существует аннулирующий многочлен с коэффициентами из , для которого является корнем, т.е. .