Предыдущая страница реферата | 15  16  17  18  19  20  21  22  23  24  25 | Следующая страница реферата



деления на второй и так до тех пор, пока деление завершится без остатков.

Это считается возможным, потому что остатки будут неотрицательным числом,

убывают, что бесконечным быть не может.

Оформим этот процесс математически:

а= bg1+r1, 0< r1< b,

b=r1g2+r2, 0 < r2< r1,

…………..

rk-2=rk-1gk+rk, 0< rk< rk-1

rk-1=rkgk+1 rk+1=0

и докажем теорему о нахождении НОД чисел. Заметим, что НОД чисел обозначаем так:

НОД (а;в), или просто (а,в)

Теорема 5

Последний, отличный от нуля, остаток в алгебре Евклида является НОД (а;в).

Для доказательства требуется предварительно рассмотреть две леммы:

Лемма 1: а=вg+r, то (а,в)=(в,r)

(a,b)=d® aM d1bM dÞ a-bgM dÞ rM dÞ d – общий делитель в и r,

т.е., если (в,r)=d1,то d1M d (1)

(в,r)=d1® bM d1, rM d1Þ aM d1Þ d1общий делитель a и b,Þ dM d1 (2)

Из (1) и (2) следует, что d=d1

Лемма 2: аM вÞ (а,в)=в

Теперь допишем теорему. Из последнего равенства в алгоритме Евклида следует, что

(rk-1,rk)=rk. А из предпоследнего, по лемме, следует, что (rk-2,rk-1)=(rk-1,rk)=rk

Поднимаясь от равенства к равенству в алгоритме Евклида получим (а,в)=,rk

 

Что и требовалось доказать.

Рекомендуем скачать другие рефераты по теме: бесплатные конспекты, реферат на тему види.

Предыдущая страница реферата | 15  16  17  18  19  20  21  22  23  24  25 | Следующая страница реферата