Учебные материалы по математике | Алгоритм евклида для целых чисел | Matematiku5
Вузы по математике Готовые работы по математике Как писать работы по математике Примеры решения задач по математике Решить задачу по математике online

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


Замечаем, что ст 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.

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

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

,т. е .

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

Наташа

Автор

Наташа — контент-маркетолог и блогер, но все это не мешает ей оставаться адекватным человеком. Верит во все цвета радуги и не верит в теорию всемирного заговора. Увлекается «нефрохиромантией» и тайно мечтает воссоздать дома Александрийскую библиотеку.

Распродажа дипломных

 Скидка 30% по промокоду Diplom2020

А ты боишься COVID-19?

 Пройди опрос и получи промокод