Алгоритм Евклида и его применения

Алгоритм Евклида и его применения. Алгоритм Евклида. Наибольший общий делитель чисел a, b можно найти с помощью алгоритма Евклида, который состоит в следующем. Пусть 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 722 16, 72 164 8, 16 82. 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-1b. Пример.

Найти линейное представление НОД160, 72. Решение. Из второго равенства системы 2 следует, что 8 72 - 164, а из первого равенства получим, что 16 160 - 722. Из двух полученных равенств находим 8 72 - 16 4 72 - 160 - 72 2 4 -4 160 9 72. Таким образом, искомое представление НОД имеет вид 8 -4 160 9 72. 30. Связь алгоритма Евклида с непрерывными дробями. Пусть - рациональная несократимая дробь. Для разложения числа в непрерывную цепную дробь можно воспользоваться алгоритмом Евклида Следовательно откуда Непрерывные дроби можно использовать для решения различных теоретико-числовых задач. 1. Линейное представление наибольшего общего делителя Пример 1. Найти линейное представление наибольшего общего делителя чисел 59, 163. Решение.

Разложим в непрерывную дробь число 2 1, 3, 4, 1, 2. Cледовательно, можно теперь заполнить таблицу qs 2 1 3 4 1 2Ps 1 2 3 11 47 58 163Qs 0 1 1 4 17 21 59s1-11 -11 -1 Отсюда получаем 59 58 - 163 21 -1 или 59 -58 163 21 1. 2. Решение линейных диофантовых уравнений Как практически находить какое-нибудь решение линейного неопределенного уравнения ax by c при a, b1, c1 Можно воспользоваться алгоритмом Евклида, из которого легко получить линейное представление НОД чисел a, b, или представить дробь в виде последней подходящей, откуда aQn - bPn -1n. Пример.

Решить диофантово уравнение 163x 59y 1. Решение. Мы проверили раньше, что 163 21 59 -58 1, следовательно, общее решение имеет вид 6.