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

Категория: Математика
Нажмите для полного просмотра!
Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №1Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №2Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №3Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №4Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №5Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №6Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №7Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №8Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №9Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №10Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №11Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №12Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №13Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа, слайд №14
Скачать
Вы можете ознакомиться и скачать презентацию на тему Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа. Доклад-сообщение содержит 14 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


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

Слайд 2


Задача 1 Камин в комнате необходимо выложить отделочной плиткой квадратной формы. Сколько плиток понадобится для камина размером 195ˣ156 см. Каковы наибольшие размеры плитки? Решение: 195∙156=30420 (см²) – S поверхности камина НОД (195 и 156)=39 (см) – сторона плитки 39 ∙39=1521 (см²) – S одной плитки 30420:1521=20 (штук) Ответ: 20 плиток размером 39ˣ39 см.
Описание слайда:
Задача 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
Описание слайда:
НОД Определение 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 теплоход
Описание слайда:
Задача 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
Описание слайда:
НОК Определение 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
Описание слайда:
Лемма Если 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
Описание слайда:
Алгоритм Евклида Пусть 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 Из теоремы следует существование НОД двух чисел, если хотя бы одно из них не равно нулю
Описание слайда:
Теорема Последний не равный нулю остаток в алгоритме Евклида, применённый к целым числам 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)
Описание слайда:
Свойства НОД Если 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 и b и выразим его линейно через эти числа 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 и выразим его линейно через эти числа 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

Слайд 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
Описание слайда:
Свойства НОК [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 – попарно взаимно простые числа, так как взаимно простые каждые два числа этого ряда
Описание слайда:
Взаимно простые числа Числа 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
Описание слайда:
Свойства взаимно простых чисел (Признак взаимно простых чисел) (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

Слайд 14


Свойства взаимно простых чисел 3) Если ab⁞c и (a, c)=1, то b⁞c Доказательство. Существуют целые числа u, v, что au+cv=1. Умножим обе части равенства на b: abu+cbv=b. Так как ab⁞c и с⁞c, то ((ab)u+cbv)⁞c, то есть b⁞c 4) Если a⁞b, a⁞c и (b, c)=1, то a⁞bc Доказательство. Существуют целые u, v, что bu+cv=1. Умножим обе части равенства на a: abu+acv=a. Так как a⁞c, b⁞b, то ab⁞bc. Так как a⁞b, c⁞c, то ac⁞bc. Следовательно, (abu+acv)⁞bc и a⁞bc
Описание слайда:
Свойства взаимно простых чисел 3) Если ab⁞c и (a, c)=1, то b⁞c Доказательство. Существуют целые числа u, v, что au+cv=1. Умножим обе части равенства на b: abu+cbv=b. Так как ab⁞c и с⁞c, то ((ab)u+cbv)⁞c, то есть b⁞c 4) Если a⁞b, a⁞c и (b, c)=1, то a⁞bc Доказательство. Существуют целые u, v, что bu+cv=1. Умножим обе части равенства на a: abu+acv=a. Так как a⁞c, b⁞b, то ab⁞bc. Так как a⁞b, c⁞c, то ac⁞bc. Следовательно, (abu+acv)⁞bc и a⁞bc

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию