Алгоритм евклида для целых чисел
Замечаем, что ст 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.
Расмотрим рав-ва алгоритма начиная с последнего .
Поскольку ,то
,кроме того
,т. е
.
Аналогично получаем, что ,
,
. Получили
Узнать стоимость за 15 минут
Распродажа дипломных
Скидка 30% по промокоду Diplom2020
Подпишись на наш паблик в ВК
Нужна работа?
Контрольная у наших партнеров