Преглед на кода на Най-малко общо кратно

В [[аритметика]]та и [[Теория на числата|теорията на числата]], '''най-малко общо кратно''' на две различни от нула [[цели числа]] ''a'' и ''b'' е най-малкото цяло положително число, което може да се раздели както на ''a'', така и на ''b''.<ref>{{cite book | last1 = Hardy | first1 = G. H. | last2 = Wright | first2 = E. M. | title = An Introduction to the Theory of Numbers |edition=5th | publisher = Oxford University Press | location = Oxford | year = 1979| isbn = 978-0-19-853171-5| url = https://books.google.com/books?id=3hTeH5VUheAC&dq&printsec=frontcover |page=48}}</ref> <ref>{{cite book | first1 = Calvin T. | last1 = Long | year = 1972 | title = Elementary Introduction to Number Theory | edition = 2nd | publisher = D. C. Heath and Company | location = Lexington | lccn = 77 – 171950 |page=39}}</ref>

Дадени са две цели числа ''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-ва степен:

<math>a=p_1^{r_1} \dots p_k^{r_k}, b=p_1^{q_1} \dots p_k^{q_k}, q_i \ge 0, r_i \ge 0 (i=1,\dots,k)</math>

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

<math>[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)}</math>

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

<math>[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</math>

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

== Източници ==
<references/>

{{нормативен контрол}}

[[Категория:Алгебра]]
[[Категория:Теория на числата]]