Определение

Наименьшее общее кратное (НОК)

a, b - integers

$lcm(a, b) = x \iff (a\space|\space x) \space\land\space (b\space|\space x) \space\land\space (x - min)$

Алгоритм нахождения

Theorem: $lcm(a, b) = \frac{a*b}{gcd(a, b)}$

Proof: suppose x is LCM of a and b:

x = a*k1

x = b*k2

⇒ x * x = a * b * k1 * k2

suppose d = gcd(a, b)

a = d*k3

b = d*k4

⇒ x*x = a * b * k1 * k2 = d * d * k1 * k2 * k3 * k4 = d$^2$ * k1 * k2 * k3 * k4

a | (d$^2$ * k1 * k2 * k3 * k4) and b | (d$^2$ * k1 * k2 * k3 * k4)

but also (reduce d’s degree) a | (d * k1 * k2 * k3 * k4) and b | (d * k1 * k2 * k3 * k4), this is actually LCM ⇒ we should just divide a*b on d, which is gcd(a, b).