Программа государственного экзамена по математике для студентов математического факультета Московского городского педагогического университета
Категория реферата: Рефераты по математике
Теги реферата: дипломы грамоты, реферат на тему общество
Добавил(а) на сайт: Aleksandra.
Предыдущая страница реферата | 2 3 4 5 6 7 8 9 10 11 12 | Следующая страница реферата
Пусть b>0. Разделим a на b, тогда по теореме о делении с остатком: a = bq1 + r1.
Если r1 = 0, то НОД(a, b) = b.
Если r1 ( 0, то разделим b с остатком на r1: b = r1q2 + r2.
Если r2 = 0, то процесс деления закончим, а если r2 ( 0, то разделим r1 с остатком на r2 : r1 = r2q3 + r3.
Продолжая далее таким же образом, мы закончим процесс деления как только получится остаток равный 0.
Заметим, что такой остаток обязательно получится. В самом деле, остаток всегда меньше делителя, поэтому b > r1 > r2 > r3 > . . . и число получаемых остатков не превосходит b.
Итак, в результате указанного алгоритма получим, что:
| |a = bq1 + r1 , | |
| |b = r1 q2 + r2 , | |
| |r1 = r2 q3 + r3 , |(1) |
| |. . . . . . . . . . . . . | |
| |rn-2 = rn-1 qn-1 + rn , | |
| |rn-1 = rn qn . | |
Тогда на основании свойств 20 и 10 :
НОД(a, b) = НОД(b, r1) = НОД(r1, r2) = . . . = НОД(rn-1, rn) = rn.
Следовательно, наибольший общий делитель чисел a и b совпадает с последним ненулевым остатком rn в алгоритме Евклида для чисел a и b.
Пример. Найти НОД(160, 72).
Применим к данным числам алгоритм Евклида:
160 = 72(2 + 16, 72 = 16(4 + 8, 16 = 8(2.
(2)
Следовательно, НОД(160, 72) = 8.
20. Теорема (о линейном представлении НОД). Если d - наибольший общий делитель чисел a и b, то существуют такие целые числа x и y, что выполняется равенство: d = xa + yb.
( Допустим, что числа a и b связаны следующими соотношениями:
| |a = bq1 + r1 , |
| |b = r1 q2 + r2 , |
| |r1 = r2 q3 + r3 , |
| |. . . . . . . . . . . . . |
| |rn-2 = rn-1 qn-1 + rn . |
Докажем, что каждое из чисел rk линейно выражается через a и b с целыми
коэффициентами. Для r1 утверждение тривиально: r1 = a - bq1 . Считая, что
каждое из чисел r1 , r2 , . . . , rn-1 является целочисленной линейной
комбинацией чисел a и b (rk = (k a + (k b), имеем rn = (n-2 a + (n-2 b - ((n-1 a + (n-1 b) qn-1 = ((n-2 - (n-1) a + ((n-2
- (n-1 qn-1)b. (
Пример. Найти линейное представление НОД(160, 72).
Решение. Из второго равенства системы (2) следует, что 8 = 72 - 16(4, а
из первого равенства получим, что 16 = 160 - 72(2. Из двух полученных
равенств находим: 8 = 72 - 16 ( 4 = 72 - (160 - 72 ( 2) ( 4 = (-4) ( 160 +
9 ( 72.
Таким образом, искомое представление НОД имеет вид:
8 = (-4) ( 160 + 9 ( 72.
30. Связь алгоритма Евклида с непрерывными дробями. Пусть ( - рациональная несократимая дробь [pic]. Для разложения числа ( в непрерывную цепную дробь можно воспользоваться алгоритмом Евклида:
[pic]
[pic]
Следовательно, [pic] , откуда[pic]
Непрерывные дроби можно использовать для решения различных теоретико- числовых задач.
1. Линейное представление наибольшего общего делителя
Рекомендуем скачать другие рефераты по теме: образец курсовой работы, как сделать шпаргалку.
Предыдущая страница реферата | 2 3 4 5 6 7 8 9 10 11 12 | Следующая страница реферата