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

Реклама. Продолжение ниже
Лекция 2 НОД и НОК. Алгоритм Евклида. Взаимно простые числа
Задача 1 Камин в комнате необходимо выложить отделочной плиткой квадратной формы. Сколько плиток понадобится для камина размером 195 ˣ 156 см. Каковы
НОД
Задача 2 В портовом городе начинаются три туристических теплоходных рейса, первый из которых длится 15 суток, второй – 20 и третий – 12 суток. Вернувшись в
НОК
Лемма Если a, b ϵ Z, b ≠0 и a = bq + r, то ( a, b )=( b, r )
Алгоритм Евклида
Теорема Последний не равный нулю остаток в алгоритме Евклида, применённый к целым числам a и b, где b ≠0, есть их наибольший общий делитель (НОД)
Свойства НОД
Примеры Найдём НОД чисел a и b и выразим его линейно через эти числа
Свойства НОД
Свойства НОД
Свойства НОК
Взаимно простые числа
Свойства взаимно простых чисел
Свойства взаимно простых чисел
Лекция 2 НОД и НОК. Алгоритм Евклида. Взаимно простые числа
1/17
Средняя оценка: 4.9/5 (всего оценок: 49)
Код скопирован в буфер обмена
Скачать (143 Кб)
Реклама. Продолжение ниже
1

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

Изображение слайда
Изображение для работы со слайдом
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/2
3

Слайд 3: НОД

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

Изображение слайда
Изображение для работы со слайдом
1/2
4

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

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

Изображение слайда
Изображение для работы со слайдом
1/2
5

Слайд 5: НОК

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

Изображение слайда
Изображение для работы со слайдом
1/2
6

Слайд 6: Лемма Если a, b ϵ Z, b ≠0 и a = bq + r, то ( a, b )=( b, r )

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

Изображение слайда
1/1
7

Слайд 7: Алгоритм Евклида

Пусть a, b ϵ Z, b ≠0. По теореме о делении с остатком a = bq 1 + r 1, где 0 ≤ r 1 < │ b │. Если r 1 ≠0, то b = r 1 q 2 + r 2, где 0 ≤ r 2 < r 1. Если r 2 ≠0, то r 1 = r 2 q 3 + r 3, где 0 ≤ r 3 < r 2. И так далее …………...... r n-2 =r n-1 q n +r n, где 0 < r n < r n-1 r n -1 = r n q n +1 + r n +1 Этот процесс не может быть бесконечным, так как не может быть бесконечной убывающей последовательности неотрицательных чисел: │ b │> r 1 > r 2 >…> r n, r n +1 ϵ [0, │ b │ ] Поэтому после нескольких шагов получим остаток, равный нулю Пусть r n +1 =0

Изображение слайда
Изображение для работы со слайдом
1/2
Реклама. Продолжение ниже
8

Слайд 8: Теорема Последний не равный нулю остаток в алгоритме Евклида, применённый к целым числам a и b, где b ≠0, есть их наибольший общий делитель (НОД)

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

Изображение слайда
1/1
9

Слайд 9: Свойства НОД

Если a⁞b, то (a, b) = │b│ НОД двух чисел линейно выражается через эти числа То есть если ( a, b ) = d, то существуют u, v ϵ Z, что d = au + bv (линейная форма НОД)

Изображение слайда
Изображение для работы со слайдом
1/2
10

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

a =1173, b =323; a = 3∙ b + r 1, r 1 =204; b =1∙ r 1 + r 2, r 2 =119; r 1 = r 2 + r 3, r 3 =85; r 2 = r 3 + r 4, r 4 =34; r 3 =2∙ r 4 + r 5, r 5 =17; r 4 =2∙ r 5. Итак, ( a, b )= d =17. Выразим его линейно через a и b. Из первого равенства r 1 = a -3 b. Подставив в равенство для b, находим r 2 = b - r 1 =- a +4 b. Далее : r 3 =r 1 -r 2 =2a-7b; r 4 =r 2 -r 3 =-3a+11b; d=r 5 =r 3 -2r 4 =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=-3 a+4b Примеры Найдём НОД чисел a и b и выразим его линейно через эти числа

Изображение слайда
1/1
11

Слайд 11: Свойства НОД

3) Если (a, b)=d, n ϵ N, то ( na, nb )= nd 4) Если (a, b)=d, a⁞n, b⁞n, n ϵ N, то В частности, Свойства НОД

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
12

Слайд 12: Свойства НОД

5) (a 1, a 2, …, a n ) = ((a 1, a 2, …, a n-1 ), a n ) Доказательство Пусть (a 1, a 2, …, a n )=d 1 ; ((a 1, a 2, …, a n-1 ), a n )=d 2 a 1, a 2, …, a n делятся на d 1 Следовательно, ( a 1, a 2, …, a n -1 )⁞ d 1 и a n ⁞ d 1, поэтому их НОД d 2 ⁞ d 1 Так как ( a 1, a 2, …, a n -1 )⁞ d 2 и a n ⁞ d 2, то ( a 1, a 2, …, a n ) ⁞ d 2 и их наибольший общий делитель ( a 1, a 2, …, a n ) = d 1 ⁞ d 2 Получили, что d 2 = d 1 6) Наибольший общий делитель чисел a 1, a 2, …, a n, где не все a i равны нулю, существует и единственный Существование следует из теоремы о последнем, не равном нулю остатке в алгоритме Евклида и свойства 5 Единственность – из определения НОД и свойства 6 делимости чисел Свойства НОД

Изображение слайда
1/1
13

Слайд 13: Свойства НОК

[a 1, a 2, …, a n ]=[[ a 1, a 2, …, a n-1 ], a n ] Если к – натуральное, то [ ak, bk ]= k [ a, b ] Если k = натуральное, a ⁞ k, b ⁞ k, то Если (a, b)=1, то [a, b] = ab Замечание Свойство 1 доказывается аналогично свойству 5 НОД Остальные свойства можно доказать позже, используя следствие 3 из основной теоремы арифметики

Изображение слайда
Изображение для работы со слайдом
1/2
14

Слайд 14: Взаимно простые числа

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

Изображение слайда
Изображение для работы со слайдом
1/2
Реклама. Продолжение ниже
15

Слайд 15: Свойства взаимно простых чисел

(Признак взаимно простых чисел) ( a, b )=1 тогда и только тогда, когда найдутся целые u и v, что au + bv =1 Доказательство. Необходимость следует из свойства 2 НОД (линейная форма НОД). Докажем достаточность. Пусть d=(a, b). Тогда a ⁞ d, b ⁞ d и ( au + bv )⁞ d, то есть 1⁞ d. Следовательно, d =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, то есть au 1 + bcv 1 =1 или ( a, bc )=1

Изображение слайда
1/1
16

Слайд 16: Свойства взаимно простых чисел

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

Изображение слайда
1/1
17

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

Изображение слайда
Изображение для работы со слайдом
1/2
Реклама. Продолжение ниже