Дипломная работа: Теория остатков
r n -3 = r n -2 q n -1 + r n -1
r n -2 = r n -1 q n + r n
r n -1 = r n q n +1
0 r n -1 < r n -2
0 r n < r n -1
r n +1 = 0
3. Заменить r := "остаток от деления а на b ", а := b , b := r .
4. Идти на 2.
В современной буквенной записи, алгоритм Евклида выглядит так: a > b; a, b Z .
Имеем: b > r 1 > r 2 >... > r n > 0, следовательно процесс оборвется максимум через b шагов. Очень интересный и практически важный народохозяйственный вопрос о том, когда алгоритм Евклида работает особенно долго, а когда справляется с работой молниеносно, мы рассмотрим чуть позже. Давайте сейчас покажем, что r n = ( a , b ). Просмотрим последовательно равенства сверху вниз: всякий делитель а и b делит r 1 , r 2 ,..., r n . Если же просматривать эту цепочку равенств от последнего к первому, то видно, что r n | r n -1 , r n | r n -2 , и т.д., т.е. r n делит а и b . Поэтому r n - наибольший общий делитель чисел а и b .
Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и b совпадает с совокупностью делителей ( a , b ). Еще он дает практический способ нахождения чисел u и v из Z (или, если угодно, из теоремы пункта 2) таких, что r n = au + bv = ( a, b ).
Действительно, из цепочки равенств имеем:
r n = r n -2 - r n -1 q n = r n -2 - ( r n -3 - r n -2 q n -1 ) q n = ...
(идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение)
... = au + bv = ( a , b ).
Пример. Пусть а = 525, b = 231. (ниже приводится запись деления уголком, и каждый раз то, что было в уголке, т.е. делитель, приписывается к остатку от деления с левой стороны, а остаток, как новый делитель, берется в уголок)
|
_ _42| 42 | 0 |
_ 63| 42 | 21 2 |
_ 231| 189 | 42 К-во Просмотров: 558
Бесплатно скачать Дипломная работа: Теория остатков
|