Компьютерный центр г. Светлогорска

НОД и НОК

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

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

С наибольшим общим делителем тесно связано понятие наименьшего общего кратного (НОК) — наименьшего целого числа, которое делится одновременно на $a$ и на $b$; оно обозначается $lcm(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(30,12)=gcd(12,6)=gcd(6,0)=6$.

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

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

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

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

Свойства НОД

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$(чётных  чисел) $\ge 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$.

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

from math import gcd

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

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

6
15
3

Найдите наименьшее общее кратное всех $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

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