Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа

Сентябрь 14, 2022

Главная
Математика
Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа

Содержание

2. Задача 1 Камин в комнате необходимо выложить отделочной плиткой квадратной формы. Сколько плиток понадобится для камина
3. НОД Определение 1. Число d называется общим делителем чисел a1, a2,…, an, если a1⁞d, a2⁞d,…, an⁞d
4. Задача 2 В портовом городе начинаются три туристических теплоходных рейса, первый из которых длится 15 суток,
5. НОК Определение 3. Число М называется общим кратным целых чисел a1, a2,…, an, если оно делится
6. Лемма Если a, b ϵ Z, b≠0 и a=bq+r, то (a,b)=(b,r) Доказательство Пусть (a,b)=d1, (b,r)=d2 Так
7. Алгоритм Евклида Пусть a, b ϵ Z, b≠0. По теореме о делении с остатком a=bq1+r1, где
8. Теорема Последний не равный нулю остаток в алгоритме Евклида, применённый к целым числам a и b,
9. Если a⁞b, то (a, b) = │b│ Если (a, b) = d, то существуют u, v
10. a=1173, b=323; a= 3∙b+r1, r1=204; b=1∙r1+r2, r2=119; r1=r2+r3, r3=85; r2=r3+r4, r4=34; r3=2∙r4+r5, r5=17; r4=2∙r5. Итак, (a,
11. Свойства НОК [a1, a2, …, an]=[[ a1, a2, …, an-1], an] Если к – натуральное, то
12. Взаимно простые числа Числа a1, a2, …, an называют взаимно простыми, если наибольший общий делитель этих
13. Свойства взаимно простых чисел (Признак взаимно простых чисел) (a, b)=1 тогда и только тогда, когда найдутся
15. Скачать презентацию

Слайд 2

Задача 1 Камин в комнате необходимо выложить отделочной плиткой квадратной формы. Сколько

плиток понадобится для камина размером 195ˣ156 см. Каковы наибольшие размеры плитки?

Решение:
195∙156=30420 (см²) – S поверхности камина
НОД (195 и 156)=39 (см) – сторона плитки
39 ∙39=1521 (см²) – S одной плитки
30420:1521=20 (штук)
Ответ: 20 плиток размером 39ˣ39 см.

Слайд 3

НОД
Определение 1. Число d называется общим делителем чисел a1, a2,…, an,

если a1⁞d, a2⁞d,…, an⁞d
Определение 2. Наибольшим общим делителем целых чисел a1, a2,…, an называется такой их общий натуральный делитель, который делится на любой их общих делитель
Обозначают: d=(a1, a2,…, an)
d=(a1, a2,…, an), если
d ϵ N
d – общий делитель чисел a1, a2,…, an
если с – общий делитель чисел a1, a2,…,an, то d⁞c
Примеры
(16, 30, 12)=2
(21, 15, 48)=3

Слайд 4

Задача 2 В портовом городе начинаются три туристических теплоходных рейса, первый из

которых длится 15 суток, второй – 20 и третий – 12 суток. Вернувшись в порт, теплоходы в этот же день снова отправляются в рейс. Сегодня из порта вышли теплоходы по всем трем маршрутам. Через сколько суток они впервые снова вместе уйдут в плавание? Какое количество рейсов сделает каждый теплоход?

Решение:
НОК (15, 20 и 12)=60 (суток) – время встречи
60:15=4 (рейса) – 1 теплоход
60:20=3 (рейса) – 2 теплоход
60:12=5 (рейсов) – 3 теплоход

Слайд 5

НОК
Определение 3. Число М называется общим кратным целых чисел a1, a2,…,

an, если оно делится на каждое из этих чисел
Определение 4. Наименьшим общим кратным целых чисел a1, a2,…, an называется такое их общее натуральное кратное m, которое делит любое их общее кратное
Обозначают: m=[a1, a2,…, an]
m=[a1, a2,…, an], если
m ϵ N
m – общее кратное чисел a1, a2,…, an
если М – общее кратное чисел a1, a2,…, an, то М⁞m
Примеры: [16, 30, 12]=16∙5∙3=240; [21, 15, 48]=48∙5∙7

Слайд 6

Лемма Если a, b ϵ Z, b≠0 и a=bq+r, то (a,b)=(b,r)
Доказательство

Пусть (a,b)=d1, (b,r)=d2
Так как a⁞d1, b⁞d1, то (r=a-bq) ⁞d1
Следовательно, d1 – общий делитель чисел b и r, поэтому их наибольший общий делитель d2=(b,r) ⁞d1
Так как b⁞d2, r⁞d2, то a⁞d2 и d2 – общий делитель чисел a и b
Поэтому d1⁞d2
Из того, что d1⁞d2, d2⁞d1 и d1, d2 ϵ N, следует, что d1=d2

Слайд 7

Алгоритм Евклида
Пусть a, b ϵ Z, b≠0. По теореме о делении

с остатком
a=bq1+r1, где 0 ≤ r1 < │b│. Если r1≠0, то
b=r1q2+r2, где 0 ≤ r2 < r1. Если r2≠0, то
r1=r2q3+r3, где 0 ≤ r3 < r2. И так далее
…………......
rn-2=rn-1qn+rn, где 0 < rn < rn-1
rn-1=rn qn+1+rn+1
Этот процесс не может быть бесконечным, так как не может быть бесконечной убывающей последовательности неотрицательных чисел:
│b│> r1 > r2 >…> rn , rn+1 ϵ [0, │b│]
Поэтому после нескольких шагов получим остаток, равный нулю
Пусть rn+1=0

Слайд 8

Теорема Последний не равный нулю остаток в алгоритме Евклида, применённый к

целым числам a и b, где b≠0, есть их наибольший общий делитель (НОД)

Доказательство
Применяя лемму к первому, второму и так далее равенствам алгоритма Евклида, имеем:
(a, b) = (b, r1) = (r1, r2) = … = (rn-1, rn) = rn, так как rn-1⁞rn
Из теоремы следует существование НОД двух чисел, если хотя бы одно из них не равно нулю

Слайд 9

Если a⁞b, то (a, b) = │b│
Если (a, b) = d,

то существуют u, v ϵ Z, что d=au+bv (линейная форма НОД)
3) Если (a, b)=d, n ϵ N, то (na, nb)=nd
4) Если (a, b)=d, a⁞n, b⁞n, n ϵ N, то
В частности,
5) (a1, a2, …, an) = ((a1, a2, …, an-1), an)

Свойства НОД

Слайд 10

a=1173, b=323; a= 3∙b+r1, r1=204; b=1∙r1+r2, r2=119; r1=r2+r3, r3=85; r2=r3+r4, r4=34;

r3=2∙r4+r5, r5=17; r4=2∙r5. Итак, (a, b)=d=17. Выразим его линейно через a и b. Из первого равенства r1=a-3b. Подставив в равенство для b, находим r2=b-r1=-a+4b. Далее: r3=r1-r2=2a-7b; r4=r2-r3=-3a+11b; d=r5=r3-2r4=8a-29b
a=1403, b=1058; 1403=1058+345; 1058=345∙3+23; 345=23∙15. НОД чисел a и b равен 23. 23=1058-345∙3=1058-(1403-1058)∙3=-3∙1403+4∙1058=-3a+4b

Примеры Найдём НОД чисел a и b и выразим его линейно через эти числа

Слайд 11

Свойства НОК
[a1, a2, …, an]=[[ a1, a2, …, an-1], an]
Если к

– натуральное, то [ak, bk]=k[a, b]
Если k = натуральное, a⁞k, b⁞k, то
Если (a, b)=1, то [a, b] = ab

Слайд 12

Взаимно простые числа
Числа a1, a2, …, an называют взаимно простыми, если

наибольший общий делитель этих чисел равен 1
Примеры
1) 15, 21, 14 – взаимно простые числа, однако эти числа не являются попарно взаимно простыми
2) 34, 53, 99, 115 – попарно взаимно простые числа, так как взаимно простые каждые два числа этого ряда

Слайд 13

Свойства взаимно простых чисел
(Признак взаимно простых чисел)
(a, b)=1 тогда и

только тогда, когда найдутся целые u и v, что au+bv=1
2) Если (a, b)=1 и (a, c)=1, то (a, bc)=1
Доказательство. Согласно признаку, существуют целые числа x, y, u, v, что ax+by=1 и au+cv=1. Перемножив эти равенства, получим a(axu+xcv+buy)+bc(yv)=1, то есть au1+bcv1=1 или
(a, bc)=1