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

Замечаем, что ст f1 < ст f=n или f1=0, т. к. f и gh1 имеют одинаковые высшие одночлены( anxn ), которые сократятся при вычитании. Останутся одночлены более низкой степени чем n.

(1)  f=g h1+ f1, ст f1< ст f=n или f1=0

Пусть ст f1≥ ст g

Тогда применяя для f1 вышерассмотренные рассужд. для f получим:

(2)  f1= g h2+ f2 , f2=0 или ст f2< ст f1

Пусть ст f2≥ ст g

Тогда к f2 применяем предыдущие рассуждения и т. д.

Заметим, что стf1 , ст f2, …, являясь целыми не отрицательными числами, удовлетворяют неравенствам: ст f> ст f1 > ст f2 > … следовательно, через конечное число шагов получим:

(3)  fк =g hk+1 + fк+1 , fк+1=0 или ст fк+1 < ст fk

ст fk+1< ст g

Теперь складываем почленно равенства (1),(2),(3)… получим

f+ f1 + …+ fk =g(h1+…+hk+1)+( f1 +…+ fk)+ fк+1 =>

f=gh+fк+1, пусть fк+1=r, f=gh+r, r=0 или, ст r< ст g.

Т. о. условия 10 и 20 выполняются. Случай 2 доказан.

II. единственность. От противного. Пусть есть два различ. деления.

f= g h1+ r1, где r1=0 или ст r1< ст g (4)

f= g h2+ r2 , где r2=0 или ст r2< ст g (5)

Пусть r1≠ r2. Тогда вычитанием получим

(6)g(h2 — h1)= r1- r2 => cт g+ ст(h1- h2 )= ст(r1- r2) => ст(r1- r2)≥ cт g(*)

С другой стороны: из неравенств 4 и 5:

ст(r1- r2)≤max{ст r1, ст r2}<ст g(**)

Получили противоречие (*) и (**) => r1= r2

Из рав-ва (6) и r1= r2 получим

Т. о. единственность доказана. И теорема доказана.

Полином h рассматриваемый в теореме будем наз-ть неполным частным, а r – остатком. Если r=0, то будем говорить, что f делиться g.

Пример: разделить мн-н на

Значит

Вопрос 12.

Алгоритм Евклида для целых чисел и многочленов. НОД и НОК.

Опр1: Целое число называется общим делителем целых чисел , если каждое из этих чисел делится на с.

Опр2: Целое число Д называется наибольшим общим делителем целых чисел , если: 1) Д>0; 2) Д-общий делитель чисел ; 3)Д делится на любой общий делитель чисел .

НОД чисел обозначается D=

Теорема1: если НОД чисел существует, то он определяется однозначно.

Д-во: пусть Д и К— НОД чисел .

Имеем: Д— общий делитель (по опр2.п 3).) .

Аналогично К— общий делитель (по опр2.п 3).) Д=К

Теорема2: НОД целых чисел равен НОД их модулей.

Замечание: Теорема позволяет в дальнейшем рассматривать НОД только неотрицательных чисел, а поскольку 0 делится на любое целое число ≠0, то при отыскании НОД целых чисел ноль отбрасываем и можно рассматривать НОД только положит целых чисел => натуральных чисел.

Покажем, что НОД любых чисел всегда существует. Это можно сделать с помощью вопроса делений с остатком, названным алгоритмом Евклида.

Алгоритм Евклида. .разделим число a на b с остатком, т. е найдем :, . Если , то процесс закончен и очевидно, что НОД чисел a, b равен b.

Пусть , тогда разделим b на r1: , ,Если r2=0, то процесс закончен, если нет, то разделим r1 на r2 с остатком.

,…

Процесс обязательно закончится, т. к остатки

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

, , .Полученную систему неравенств наз. Алгоритмом Евклида для чисел a и b.

Теорема3: Последний отличный от нуля остаток в этом алгоритме является НОД чисел a и b, т. е. (a, b)=r k

Док-во:

Покажем, что r k удовлетворяет всем 3-м условиям опр НОД

10. r k>0 выполняется

20.

Расмотрим рав-ва алгоритма начиная с последнего .

Поскольку ,то ,кроме того

,т. е .

Аналогично получаем, что ,,. Получили