Викия

Математика

Наибольший общий делитель

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Наибольшим общим делителем (НОД) двух целых чисел m и n называется их общий делитель d (т.е. d\mid m и d\mid n), который делится на любой другой общий делитель m и n. Наибольший общий делитель определён если хотя бы одно из чисел m или n не ноль. Возможные обозначения наибольшего общего делителя чисел m и n: (m,n), а иногда НОД(m,n) или GCD(m,n).

Числа m и n называются взаимно-простыми, если (m,n)=1.

Эффективным способом вычисления наибольшего общего делителя является алгоритм Евклида.

Понятие наибольшего общего делителя естественно обобщается на набор целых чисел. Он тоже вычисляется алгоритмом Евклида. Следует различать понятия взаимной простоты, когда НОД набора чисел равен 1, и попарной взаимной простоты, когда НОД равен 1 для каждой пары чисел из набора. Например, НОД(6,10,15)=1, но любые пары из этого набора не взаимно просты.

Поскольку понятие делимости целых чисел естественно обобщается на рациональные числа (например, 0.5 делится нацело на 0.25, а 0.25 на 0.5 нацело не делится), то понятия НОД и НОК распространяются и на наборы рациональных чисел.

Связанные определенияПравить

СвойстваПравить

n=p_1^{d_1}\cdot\dots\cdot p_k^{d_k},
m=p_1^{e_1}\cdot\dots\cdot p_k^{e_k},
здесь p_1,\dots,p_k — различные простые числа, а d_k\! и e_k\! неотрицательные целые числа (они могут быть нулями, если p_k\! в разложении отсутствует). Тогда НОД и НОК выражаются формулами:
(n,m)=p_1^{\min(d_1,e_1)}\cdot\dots\cdot p_k^{\min(d_k,e_k)}
[n,m]=p_1^{\max(d_1,e_1)}\cdot\dots\cdot p_k^{\max(d_k,e_k)}
  • Для любых m и n
         (n,m)\cdot[n,m]=n\cdot m
    это частный случай более общей теоремы:
    • Если D, a_1, a_2, \dots , a_n — ненулевые рациональные числа, тогда
          [a_1, a_2, \dots , a_n]=D/(D/a_1, D/a_2, \dots , D/a_n)
  • Наибольший общий делитель чисел m и n может быть определен как наименьший положительный элемент всех их линейных комбинаций:
\left\{ a\cdot m + b\cdot n\mid a,b\in\Z \right\}
и, таким образом (m,n) представим в виде линейной комбинации чисел m и n:
(m,n) = u\cdot m + v\cdot n.
Это соотношение называется соотношением Безу, а коэффициенты u и v — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы \mathbb{Z}, порождённая набором \{a_1, a_2, \dots , a_n\}, — циклическая и порождается одним элементом (a_1, a_2, \dots , a_n).bg:Най-голям общ делител

ca:Màxim comú divisor cs:Největší společný děliteleo:Plej granda komuna divizorofa:بزرگ‌ترین مقسوم علیه مشترکhe:מחלק משותף מקסימלי id:Faktor persekutuan terbesarlv:Lielākais kopīgais dalītājs nl:Grootste gemene deler no:Største felles faktor pl:Największy wspólny dzielniksl:Največji skupni delitelj sr:Највећи заједнички делилац sv:Största gemensamma delare th:ตัวหารร่วมมาก ur:عاد اعظم

Викия-сеть

Случайная вики