Наибольший общий делитель и наименьшее общее кратное

Определение: Наибольшим общим делителем двух или нескольких натуральных чисел называют наибольшее натуральное число, на которое делится каждое из данных чисел.

Например

НОД

Взаимно простые числа

Определение: Два натуральных числа называются взаимно простыми, если их НОД равен единице.

Нахождение НОД с помощью разложения на простые множители

Чтобы найти НОД двух или нескольких чисел, необходимо:

1. Разложить данные числа на простые множители.
2. Составить произведение из общих простых множителей, взятых с наименьшим показателем степени.
3. Найти значение произведения.

Алгоритм Евклида

1. Поделить на с остачею:
   
2. Разделить делитель на :
   
3. Разделить делитель на новую остаток :
   

Последняя отличная от нуля остаток и есть НОД.

Наименьшее общее кратное (НОК)

Наименьшим общим кратным двух или нескольких натуральных чисел называют наименьшее натуральное число, которое делится на каждое из данных чисел.

Нахождение нок двух натуральных чисел

Чтобы найти нок двух или нескольких чисел, необходимо:

HCK

Например

НСК

Связь между НОД и нок двух чисел

НОД