Лекция НОД и НОК двух чисел,алгоритм Евклида

НОД и НОК двух чисел, алгоритм Евклида Наибольший общий делитель Наибольшее натуральное число , на которое делятся без остатка числа a и b  называется наибольшим общим делителем и часто обозначается НОД. Определение Если натуральное число a делится на натуральное число b, то b называют  делителем числа a, а число a называют кратным числа b Пусть a и b­натуральные числа. Число с называют общим делителем и для а и  для b. Множество общих делителей чисел a и b конечно,так как ни один из этих  делителей не может быть больше ,чем a. Значит ,среди этих делителей есть  наибольший, который называют наибольшим общим делителем чисел a и b и   для его обозначения используют записи : НОД(а;b)   или D(a;b) Чтобы найти наибольший общий делитель двух чисел необходимо: 1)разложить числа на простые множители 2)Выбрать числа, которые входят в разложение этих чисел 3)Найти произведение чисел , найденных на шаге 2.Полученное число и будет  искомым наибольшим общим делителем. Пример 1: найти НОД чисел 121 и 132 Будем находить согласно представленному алгоритму. Для этого 1) разложить числа на простые множители                       242=2*11*11                                      132=2*2*3*11 2)Выбрать числа, которые входят в разложение этих чисел                       242=2*11*11                                      132=2*2*3*11 3)Найти произведение чисел , найденных на шаге 2.Полученное число и будет  искомым наибольшим общим делителем. НОД=2*11=22 Пример 2. найти НОД одночленов     63 и   81 Будем находить согласно представленному алгоритму. Для этого 1)разложим числа на простые множители 63=3*3*7                    81=3*3*3*3        2) Выбираем числа, которые входят в разложение этих чисел 63=3*3*7                    81=3*3*3*3 3)Найдем произведение чисел , найденных на шаге 2.Полученное число и  будет искомым наибольшим общим делителем. НОД=3*3=9 Найти НОД двух чисел можно и по­другому, используя множество делителей  чисел Пример 3.Найти НОД чисел 48   и 60 Решение : Найдем множество делителей числа 48:  {1,2,3.4.6,8,12,16,24,48} Теперь найдем множество делителей числа 60: {1,2,3,4,5,6,10,12,15,20,30,60} {1,2,3,4,6,12} ­ данное множество  Найдем пересечение этих множеств :  будет определять множество общих делителей чисел 48 и 60. Наибольший  элемент в данном множестве будет число 12. Значит наибольший общий  делитель чисел 48 и 60 будет 12 D(48;60)=12 Определение НОК Общим кратным натуральных чисел a и b называется натуральное число,  которое кратно и a и b. Общими кратными чисел называются числа которые делятся на исходные без  остатка.Например для чисел 25 и 50 общими кратными будут числа  50,100,150,200 и т.д Наименьшее из общих кратных будет называться наименьшим общим кратным и обозначается НОК(a;b)  или K(a;b) Чтобы найти НОК двух чисел необходимо: 1) разложить числа на простые множители 2) Выписать множители, входящие в состав первого числа и добавить к  ним множители, которые входят в состав второго и не ходят в состав  первого 3) Найти произведение чисел , найденных на шаге 2.Полученное число и  будет искомым наименьшим общим кратным Пример 3: Найти НОК чисел 99 и 77 Будем находить согласно представленному алгоритму. Для этого 1) разложить числа на простые множители 99=3*3*11                               77=7*11      2)Выписать множители, входящие в состав первого                         3,3,11    добавить к ним множители, которые входят в состав второго и не ходят  в состав первого                        7 3)Найти произведение чисел , найденных на шаге 2.Полученное число и  будет искомым наименьшим общим кратным                       НОК=3*3*11*7=693  Составление списков делителей чисел часто очень трудоемкое занятие.  Существует способ нахождение НОД, называемый алгоритмом Евклида. Утверждения ,на которых основан алгоритм Евклида 1)Если a и b –натуральные числа, причем a ⋮ b, то D(a;b)=b 2) Если a и b –натуральные числа, такие что b‹a ,то D(a;b)= D(a­b;b). Пользуясь D(a;b)= D(a­b;b),можно последовательно уменьшать  рассматриваемые числа до тех пор, пока не дойдем до такой пары чисел, что  одно из них делится на другое. Тогда меньшее из этих чисел и будет искомым  наибольшим общим делителем для чисел a и b Свойства НОД и НОК 1)Любое общее кратное чисел a и b делится на K(a;b) 2)Если a ⋮ b , то К(a;b)=a  3)Если К(a;b)=k и m­натуральное число, то К(am;bm)=km Если d­общий делитель для a и b,то К( ;b a d )= d k d    4)Если a ⋮ c и b ⋮ c ,то  ab c   ­ общее кратное чисел a и b 5)Для любых натуральных чисел a и b выполняется равенство  D(a;b)* К(a;b)=ab 6)Любой общийй делитель чисел a и b является делителем числа D(a;b)