Наибольший общий делитель двух натуральных чисел a и b – наибольший из всех общих делителей a и b.

Обозначения: НОД(a,b); gcd(a,b); (a,b).

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

Обозначения: НОК(a,b); lcm(a,b); [a,b].

НОД эффективно находить, используя алгоритм Евклида. В библиотеке cmath языка C++ предусмотрена функция __gcd, вычисляющая НОД своих аргументов. Однако, не составит труда самостоятельно реализовать алгоритма Евклида:

Для вычисления НОК можно воспользоваться формулой a×b = НОД(a,b)×НОК(a,b), из которой получаем, что