Авторизация

НОД и НОК

Наибольшим общим делителем (НОД) целых чисел \(a\) и \(b\) называется наибольшее целое число, которое делит одновременно \(a\) и \(b\). Например, \(gcd(30, 12) = 6\).

 

Числа \(a\) и \(b\) называются взаимно простыми тогда и только тогда, когда они не имеют общих делителей отличных от \(1\). То есть в их отношении должно выполняться условие \(gcd(a, b) = 1\).

 

С наибольшим общим делителем тесно связано понятие наименьшего общего кратного (НОК) — наименьшего целого числа, которое делится одновременно на \(a\) и на \(b\); оно обозначается \(lcm(a, b)\). Формулу

 

\(lcm(a, b) = \frac{ab}{gcd(a,b)}\)

 

можно использовать для вычисления наименьшего общего кратного. Например, \(lcm(30, 12) = \frac{360}{gcd(30,12)} = 60\)

 

Один из способов нахождения \(gcd(a, b)\) — разложить \(a\) и \(b\) на простые множители, а затем для каждого простого числа взять наибольшую степень, в которой оно входит в оба разложения. Так, чтобы вычислить \(gcd(30, 12)\), мы можем построить разложения \(30 = 2 \cdot 3 \cdot 5\) и \(12 = 2^2 \cdot 3\), а затем сделать вывод, что \(gcd(30, 12) = 2 \cdot 3 = 6\). Однако для больших  \(a\) и \(b\)  этот метод неэффективен.

 

Алгоритм Евклида дает эффективный способ вычисления \(gcd(a, b)\). Он основан на формуле:

 

\(gcd(a, b) = \begin{cases} a & b = 0\\ gcd(b, a\; \mathrm{mod}\;b) & b \neq 0 \end{cases}\)

 

Например, \(gcd(30, 12) = gcd(12, 6) = gcd(6, 0) = 6\).

 

Этот алгоритм можно реализовать следующим образом:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

Это быстрый алгоритм: при любых \(a, b \leq 2 · 10^9\), он вычисляет их наибольший общий делитель мгновенно. Для значений в этом диапазоне количество итераций цикла while не превышает сотни.

 

Функции \(gcd\) и \(lcm\) обобщаются для произвольного числа аргументов последовательным применением:

 

\(gcd(a, b, c, d) = gcd(gcd(gcd(a, b), c), d)\)

\(lcm(a, b, c, d) = lcm(lcm(lcm(a, b), c), d)\)

Свойства НОД

  1. Коммутативность: \(gcd(a,b) = gcd(b, a)\).
  2. Ассоциативность: \(gcd(a,gcd(b,c))=gcd(gcd(a,b), c).\)
  3. \(gcd(a,b) = gcd(a - b, b).\)
  4. Наибольший общий делитель \(m\) и \(n\) делится на любой общий делитель этих чисел. Пример: для чисел \(12\) и \(18\) наибольший общий делитель равен \(6\); он делится на все общие делители этих чисел: \(1, 2, 3, 6.\)
  5. Если \(a\) делится на \(b\), то \(gcd(a, b) = b\). В частности, \(gcd(a, a) = a.\)
  6. Если \(a\) и \(b\) — взаимно простые числа, то \(gcd(a, b) = 1.\)
  7. \(gcd(1, a) = 1.\)
  8. \(gcd(a, a + 1) = 1.\)
  9. \(gcd\)(чётных  чисел) \(\geq 2\).

Свойства НОК

  1. Коммутативность: \(lcm(a,b) = lcm(b, a)\).
  2. Ассоциативность: \(lcm(a,lcm(b,c))=lcm(lcm(a,b), c).\)
  3. Если \(a\) делится на \(b\), то \(lcm(a, b) = a\). В частности, \(lcm(a, a) = a.\)
  4. Если \(a\) и \(b\) — взаимно простые числа, то \(lcm(a, b) = a \cdot b.\)
  5. \(lcm(1, a) = a.\)
  6. \(lcm(a, a + 1) = a \cdot (a + 1).\)

 

Для нахождения НОД и НОК в Python можно использовать функции \(gcd\) и \(lcm\) из математического модуля \(math\).

Пример 1

Найдите наибольший общий делитель чисел \(a\) и \(b\).

from math import gcd

a = int(input())
b = int(input())

nod = gcd(a, b)
print(f"{nod}")
6
15
3

Пример 2

Найдите наименьшее общее кратное всех \(n\) чисел.

from math import lcm

n = int(input())
a = list(map(int, input().split()))

nok = lcm(*a)
print(f"{nok}")
4
50 20 40 100
200

Практические задания