Программа государственного экзамена по математике для студентов математического факультета Московского городского педагогического университета — страница 6

  • Просмотров 2571
  • Скачиваний 217
  • Размер файла 88
    Кб

Заметим, что такой остаток обязательно получится. В самом деле, остаток всегда меньше делителя, поэтому 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 = ak a + bk b), имеем rn = an-2 a + bn-2 b - (an-1 a + bn-1 b) qn-1 = (an-2 - an-1) a + (bn-2 - bn-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. Связь алгоритма Евклида с непрерывными дробями. Пусть a - рациональная несократимая дробь числа a в непрерывную цепную дробь можно воспользоваться алгоритмом Евклида: Следовательно, , откуда Непрерывные дроби

можно использовать для решения различных теоретико-числовых задач. 1. Линейное представление наибольшего общего делителя Пример 1. Найти линейное представление наибольшего общего делителя чисел (59, 163). Решение. Разложим в непрерывную дробь число Cледовательно, можно теперь заполнить таблицу: qs 2 1 3 4 1 2 Ps 1 2 3 11 47 58 163 Qs 0 1 1 4 17 21 59 es +1 -1 +1 -1 +1 -1 Отсюда получаем 59 × 58 - 163 × 21 = -1 или 59 × (-58) + 163 × 21 = 1. 2. Решение линейных диофантовых

уравнений Как практически находить какое-нибудь решение линейного неопределенного уравнения ax + by = c при (a, b)=1, c=1 ? Можно воспользоваться алгоритмом Евклида, из которого легко получить линейное представление НОД чисел a, b, или представить дробь в виде последней подходящей aQn - bPn = (-1)n . Пример. Решить диофантово уравнение 163x + 59y = 1. Решение. Мы проверили раньше, что 163 × 21 + 59 × (-58) = 1, следовательно, общее решение имеет вид: 6. Базис