2.Нод чисел, его свойства, алгоритм Евклида. Нок чисел.

НОД целых чисел n и m называется наибольшее натуральное число, на которое делятся n и m. НОК является наименьшее натуральное число, которое делится на n и m. Два целых числа называются взаимно простыми, если НОД = 1. НОД(m,n)= НОК(m,n)=

Свойства НОД и НОК:

1)d – общий делитель m и n, НОД(m,n) ;

2)K – кратное n и m, НОК(n,m) K; 3)m>0, n>0, m n=НОД(m,n) НОК(n,m);

4)Линейное представление наибольшего общего делителя НОД(m,n)=d=>

=> ; Алгоритм Евклида (поиска НОД) m>n

1)Делим m на n с остатком

2)n делим на остаток с остатком

3) с остатком ….

k-1)

k) (НОД – последний ненулевой остаток: )