Найменше спільне кратне

• НСК(a, b) = НСК(b, a) (перестановка аргументів не змінює НСК);

• НСК(a, b, c, d) = НСК(НСК(a, b), НСК(c, d));

• НСК(a, b) = |ab|/НСД(a, b), де НСД(a, b) — найбільший спільний дільник чисел a, b.

Нехай розклад чисел на прості множники

${\displaystyle a=2^{q_{2}}\cdot 3^{q_{3}}\cdot \ldots \cdot p_{k}^{q_{p_{k}}};}$

${\displaystyle b=2^{r_{2}}\cdot 3^{r_{3}}\cdot \ldots \cdot p_{k}^{r_{p_{k}}}.}$

Тоді

НСК${\displaystyle (a,b)=2^{\max(q_{2};r_{2})}\cdot 3^{\max(q_{3};r_{3})}\cdot \dots \cdot p_{k}^{\max(q_{p_{k}};r_{p_{k}})}.}$

Визначимо НСК${\displaystyle (840,396)}$ .Розклад на прості множники:

${\displaystyle 840=2^{3}\cdot 3\cdot 5\cdot 7,}$

${\displaystyle 396=2^{2}\cdot 3^{2}\cdot 11;}$

або, подаючи для наочності нульові степені,

${\displaystyle 840=2^{3}\cdot 3^{1}\cdot 5^{1}\cdot 7^{1}\cdot 11^{0},}$

${\displaystyle 396=2^{2}\cdot 3^{2}\cdot 5^{0}\cdot 7^{0}\cdot 11^{1}.}$

Отже,

НСК${\displaystyle (840,396)=2^{3}\cdot 3^{2}\cdot 5^{1}\cdot 7^{1}\cdot 11^{1}=27720.}$

НСК можна теж обчислити за допомогою рівності НСК(a, b) =|ab|/НСД(a, b), використавши для обчислення НСД ефективний алгоритм Евкліда

int lcm(int a, int b){  return (a*b) / gcd(a, b) ;}

gcd — НСД

• Дональд Кнут. Seminumerical Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 2. — 762 с. — ISBN 0-201-89684-2.(англ.)