Группы геометрических преобразований. Группы вращений, подобий, гомотетий с заданным общим центром, параллельных переносов
Арифметические функции: t(n), s(n), j(n)
Алгоритм Евклида и его применения
Линейное представление наибольшего общего делителя
Базис пространства решений однородной системы линейных уравнений - это фундаментальная система решений
Корни многочлена; схема Горнера; теорема Безу
Разложение многочлена в произведение неприводимых
Теорема о строении простого алгебраического расширения
Навигация
Алгоритм Евклида и его применения
Программа государственного экзамена по математике для студентов математического факультета Московского городского педагогического университета
38950
знаков
13
таблиц
4
изображения
4. Алгоритм Евклида и его применения
10. Алгоритм Евклида. Наибольший общий делитель чисел 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-1qn-1+ rn , |
|
|
| rn-1 = rnqn . |
|
Тогда на основании свойств 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-1qn-1+ rn . |
Докажем, что каждое из чисел rk линейно выражается через a и b с целыми коэффициентами. Для r1 утверждение тривиально: r1 = a - bq1 . Считая, что каждое из чисел r1 , r2 , . . . , rn-1 является целочисленной линейной комбинацией чисел a и b (rk = ak a + bkb), имеем
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 в непрерывную цепную дробь можно воспользоваться алгоритмом Евклида:
Следовательно, 
,
откуда
Непрерывные дроби можно использовать для решения различных теоретико-числовых задач.
Похожие работы
... учебного процесса методической подготовки будущего учителя. Основное содержание исследования отражено в следующих публикациях автора: I. Монографии: 1. Абдуразаков М.М. Совершенствования содержания подготовки будущего учителя информатики в условиях информатизации образования. –Махачкала: ДГПУ, 2006. –190 с. 12 п.л. 2. Гаджиев Г.М., Абдуразаков М.М. Технология преподавания информатики. – ...
... профиля и специализации. На факультетах общественных наук предметы, входившие в минимум, изучались в расширенном объеме[4]. 2. Положение русского студенчества в конце XIX начале XX века 2.1 Образ русского студента в конце XIX начале XX века В отличие от закрытых учебных заведений, в которых учились в основном дворяне, значительное число учащихся в университетах были людьми незнатными ...
... и устойчивых требований, которые определяют характер и особенности организации коррекционно-образовательного процесса и управления познавательной деятельностью лиц с особыми образовательными потребностями. Специальная педагогика опирается на соответствующие обще- педагогические принципы организации образования и управления познавательной деятельностью, однако их реализация в системе специального ...
... покровителей, сделавших особый вклад в развитие культуры, в Европе называют медичи. Конец девятнадцатого века в России был ознаменован необычайным подъёмом культуры. В связи с этим появились в стране и те, кто этот подъём всячески поддерживал, в том числе и материально. Эти люди были в основном богатыми купцами и промышленниками, которые чувствовали необычайный прогресс в развитии культуры ...
0 комментариев