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

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

В уроке о делимости и делении с остатком изучалось отношение $d \mid a$ между двумя натуральными числами. Когда рассматривают два числа сразу, интерес представляют делители, которые у них общие, и кратные, которые у них совпадают. Любая пара натуральных чисел $a$ и $b$ имеет хотя бы один общий делитель, число $1$, и не более чем конечное множество общих делителей, поскольку ни один делитель числа $a$ не превосходит $a$; кроме того, у неё бесконечно много общих кратных, среди них произведение $ab$. Если это так, следующее определение имеет смысл.

Определение (наибольший общий делитель и наименьшее общее кратное). Наибольшим общим делителем двух натуральных чисел $a$ и $b$, который обозначается $\operatorname{\text{НОД}}(a, b)$, называется наибольшее натуральное число, делящее оба числа. Наименьшим общим кратным, которое обозначается $\operatorname{\text{НОК}}(a, b)$, называется наименьшее натуральное число, кратное обоим числам.

Второе есть наименьший элемент непустого множества натуральных чисел, который существует по принципу вполне упорядоченности. Первый есть наибольший элемент множества общих делителей, которое непусто и ограничено числом $a$; то, что непустое ограниченное сверху множество натуральных чисел имеет наибольший элемент, также следует из вполне упорядоченности: множество его верхних границ непусто и имеет наименьший элемент $M$, и $M$ принадлежит множеству, ведь иначе каждый элемент был бы меньше $M$ и, поскольку между $M - 1$ и $M$ нет натуральных чисел, не больше $M - 1$, а это число было бы верхней границей, меньшей $M$ (если $M = 1$, то множество есть $\{1\}$ и содержит $M$). Например, общие делители чисел $12$ и $18$ суть $1$, $2$, $3$ и $6$, а их общие кратные суть $36$, $72$, $108$ и так далее:

Из определения сразу следуют некоторые частные случаи: $\operatorname{\text{НОД}}(a, 1) = 1$ и $\operatorname{\text{НОК}}(a, 1) = a$; $\operatorname{\text{НОД}}(a, a) = \operatorname{\text{НОК}}(a, a) = a$; и, если $a$ делит $b$, то $\operatorname{\text{НОД}}(a, b) = a$ и $\operatorname{\text{НОК}}(a, b) = b$. Кроме того, обе операции симметричны: порядок чисел не меняет результата.

Вычисление с помощью разложения на простые множители

По основной теореме арифметики каждое натуральное число, большее $1$, единственным образом раскладывается на простые множители. Удобно записывать $a$ и $b$ через одни и те же простые числа $p_1, \ldots, p_k$, допуская нулевые показатели для простых чисел, которые входят только в одно из них:

Натуральное число $d$ делит $a$ в точности тогда, когда в его разложение не входят другие простые числа, кроме простых делителей числа $a$, и каждое из них входит с показателем, не большим, чем в $a$. Отсюда следует, что $d$ делит одновременно $a$ и $b$ тогда, когда показатель каждого простого числа в $d$ не превосходит ни одного из двух показателей; поэтому наибольший общий делитель получается, если для каждого простого числа взять меньший из двух показателей. Аналогично, $m$ является общим кратным, когда показатель каждого простого числа в $m$ не меньше обоих, и наименьшее общее кратное берёт для каждого простого числа больший из двух показателей. Например:

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