Неприводимость и разложение на неприводимые многочлены

(a) Пусть Будем делить делить первый многочлен на второй столбиком. После подбора первого одночлена в частном мы сможем записать:

После подбора второго:

Возникает желание доказать по индукции, что при любом после - го шага будет равенство

База уже доказана. Если предположить, что при утверждение верно, то ясно что следующим одночленом в частном будет Далее нетрудно посчитать остаток и выписать нужное равенство при

Ограничение введено неслучайно, ведь после - го шага мы получим в остатке То есть ненулевая константа делит нужный нам НОД. Следовательно, многочлены взаимно просты.

(b) Сделаем первые два шага алгоритма Евклида:

Заметим, что эти многочлены можно разложить на скобочки:

Теперь легко видеть, что НОД этих многочленов равен