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

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

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

По-лесно намиране на НОКРедактиране

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

Например: НОК на (24 и 180)

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

 

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

 

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

 

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

ИзточнициРедактиране

  1. Hardy, G. H., Wright, E. M.. An Introduction to the Theory of Numbers. 5th. Oxford, Oxford University Press, 1979. ISBN 978-0-19-853171-5. с. 48.
  2. Long, Calvin T.. Elementary Introduction to Number Theory. 2nd. Lexington, D. C. Heath and Company, 1972. с. 39.