Наибольшее натуральное число, на которое делятся без остатка числа a и b, называют наибольшим общим делителем этих чисел. Обозначают НОД(a, b).
Рассмотрим нахождения НОД на примере двух натуральных чисел 18 и 60:
60 = 2 × 2 × 3 × 5
Вычеркнуть из первого числа, множители которых нету во втором и третьем числе, получим:
Второй способ нахождения наибольшего общего делителя с помощью алгоритма Евклида. Алгоритм Евклида является наиболее эффективным способом нахождения НОД, используя его нужно постоянно находить остаток от деления чисел и применять рекуррентную формулу.
Рекуррентная формула для НОД, НОД(a, b)=НОД(b, a mod b), где a mod b - остаток от деления a на b.
Найдем НОД(7920, 594) с помощью алгоритма Евклида, вычислять остаток от деления будем с помощью калькулятора.
Наименьшим общим кратным натуральных чисел a и b называют наименьшее натурально число, которое кратно и a, и b. Обозначают НОК(a, b).
Рассмотрим нахождения НОК на примере двух натуральных чисел 18 и 60:
60 = 2 × 2 × 3 × 5
Добавляем в первое число множители из второго и третьего числа, получим:
Если известен НОД чисел, НОК можно вычислить по формуле 
Воспользуемся формулой нахождения НОК через НОД получим:
Отношение НОК и НОД:
Ряд сходится по признаку лейбница