Най-малко общо кратно
За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел. |
![]() | Тази статия се нуждае от подобрение. Необходимо е: форматиране. Ако желаете да помогнете на Уикипедия, използвайте опцията редактиране в горното меню над статията, за да нанесете нужните корекции. |
Дадени са две цели числа a и b. Минималното естествено число d (d > 0) такова, че a|d и b|d се нарича най-малко общо кратно (НОК) на a и b.
По-лесно намиране на НОК[редактиране | редактиране на кода]
Напишете числата, на които трябва да получите НОК, отделени със запетаи, зад вертикална черта. Тъй като търсим най-малко общо кратно трябва да намерим най-малкият делител на тези числа. Например: НОК на (24 и 180)
Разлагаме само на прости множители. Т.е. НОК на две числа може да се разгледа като обединение на каноничното им разлагане на прости множители (обратно – НОД се разглежда като сечение). Нека са ни дадени числата a и b, и нека имаме техните разлагания, като и в двете разлагания участват едни и същи прости числа (тези, които се срещат в поне едно от разлаганията на a и b), като за "чуждите" множители се поставя 0-ва степен:
Тогава за НОК (бележим [a,b]) и НОД (бележим (a,b)) имаме:
От последното:
Последното дава ефективен алгоритъм за изчисляването на НОК (чрез пресмятането на НОД, за което имаме ефективен метод – алгоритъма на Евклид). Първоначалният начин изискваше разлагането на прости множители, което няма ефективно алгоритмично решение.