Най-малко общо кратно

В аритметиката и теорията на числата, най-малко общо кратно на две различни от нула цели числа a и b е най-малкото цяло положително число, което може да се раздели както на a, така и на b.

Дадени са две цели числа a и b. Минималното естествено число d (d > 0) такова, че a|d и b|d се нарича най-малко общо кратно (НОК) на a и b.

По-лесно намиране на НОК

Напишете числата, на които трябва да получите НОК, отделени с точка и запетая пред отвесна черта. Тъй като търсим най-малко общо кратно трябва да намерим най-малкият делител на тези числа.

Например: НОК на (6 и 16)

6; 16 | 2

3; 8 | 2

3; 4 | 2

3; 2 | 2

3; 1 | 3

1; 1 |

НОК = 2·2·2·2·3 = 48

Разлагаме само на прости множители. Т.е. НОК на две числа може да се разгледа като обединение на каноничното им разлагане на прости множители (обратно – НОД се разглежда като сечение). Нека са ни дадени числата a и b, и нека имаме техните разлагания, като и в двете разлагания участват едни и същи прости числа (тези, които се срещат в поне едно от разлаганията на a и b), като за „чуждите“ множители се поставя 0-ва степен:

$a=p_{1}^{r_{1}}\dots p_{k}^{r_{k}},b=p_{1}^{q_{1}}\dots p_{k}^{q_{k}},q_{i}\geq 0,r_{i}\geq 0(i=1,\dots ,k)$

Тогава за НОК (бележим [a,b]) и НОД (бележим (a,b)) имаме:

$[a,b]=p_{1}^{max(r_{1},q_{1})}\dots p_{k}^{max(r_{k},q_{k})},(a,b)=p_{1}^{min(r_{1},q_{1})}\dots p_{k}^{min(r_{k},q_{k})}$

От последното:

$[a,b](a,b)=p_{1}^{max(r_{1},q_{1})+min(r_{1},q_{1})}\dots p_{k}^{max(r_{k},q_{k})+min(r_{k},q_{k})}=p_{1}^{r_{1}+q_{1}}\dots p_{k}^{r_{k}+q_{k}}=ab$

Последното дава ефективен алгоритъм за изчисляването на НОК (чрез пресмятането на НОД, за което имаме ефективен метод – алгоритъма на Евклид). Първоначалният начин изискваше разлагането на прости множители, което няма ефективно алгоритмично решение.