Наименьшее общее кратное

Наиме́ньшее о́бщее кра́тное () двух целых чисел и есть наименьшее натуральное число, которое делится на и без остатка, то есть кратно им обоим. Обозначается одним из следующих способов:

  • ;
  • ;
  • или     (от англ. least common multiple).

Пример: .

Наименьшее общее кратное для нескольких чисел — это наименьшее натуральное число, которое делится на каждое из этих чисел.

Одно из наиболее частых применений — приведение дробей к общему знаменателю.

Свойства

  • Коммутативность: .
  • Ассоциативность: .
  • Связь с наибольшим общим делителем :
  • В частности, если и взаимно-простые числа, то
  • при
  • Наименьшее общее кратное двух целых чисел и является делителем всех других общих кратных и . Более того, множество общих кратных , совпадает с множеством кратных для .
  • Асимптотики для могут быть выражены через некоторые теоретико-числовые функции. Так:
    • функция Чебышёва
    • что следует из определения и свойств функции Ландау ;
    • что следует из закона распределения простых чисел.

Нахождение НОК

можно вычислить несколькими способами.

1. Если известен наибольший общий делитель, можно использовать его связь с :

2. Пусть известно каноническое разложение обоих чисел на простые множители:

где — различные простые числа, а и — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда вычисляется по формуле:

Другими словами, разложение содержит все простые множители, входящие хотя бы в одно из разложений чисел , причём из показателей степени этого множителя берётся наибольший. Пример для бóльшего количества чисел:

Вычисление наименьшего общего кратного нескольких чисел может быть также сведено к нескольким последовательным вычислениям от двух чисел:

См. также

Литература

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.