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

от Уикипедия, свободната енциклопедия

В аритметиката и теорията на числата, най-малко общо кратно на две цели числа 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.