Свойства НОД

• Основное свойство: наибольший общий делитель m и n делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
• Следствие 1: множество общих делителей m, n совпадает с множеством делителей НОД (m, n).
• Следствие 2: множество общих кратных m, n совпадает с множеством кратных НОК (m, n).
• Если m делится на n, то НОД (m, n) = n. В частности, НОД (n, n) = n.
• — общий множитель можно выносить за знак НОД.
• Если D = (m, n), то после деления на D числа становятся взаимно простыми, то есть, . Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
• Мультипликативность: если a ₁, a ₂ взаимно просты, то:

• Наибольший общий делитель чисел m и n может быть определён как наименьший положительный элемент множества всех ихлинейных комбинаций:

и поэтому (m, n) представим в виде линейной комбинации чисел m и n:

.

Это соотношение называется соотношением Безу, а коэффициенты u и v — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы , порождённая набором , — циклическая и порождается одним элементом: НОД .