42
правки
Изменения
Нет описания правки
<tex>\gcd(A) = \max \left\{ d \mid \forall a_j \in A,\: a_j \equiv 0 \left(\bmod d \right)\right\}</tex>
}}
Существует определение НОД через [[Разложение_на_множители_(факторизация) | разложение числа на простые множители]]:
{{Утверждение
|id=l001
|statement=
Пусть <tex>a</tex> и <tex>b</tex> - натуральные числа. Тогда <tex dpi="140">\gcd(a, b) = p_1^{\min(\alpha_1, \beta_1)}\cdot p_2^{\min(\alpha_2, \beta_2)} \cdot \dotso \cdot p_k^{\min(\alpha_k, \beta_k)}</tex>
|proof=
Очевидно, что в таком случае <tex>a</tex> и на <tex>b</tex> делятся на <tex dpi="140">p = p_1^{\min(\alpha_1, \beta_1)}\cdot p_2^{\min(\alpha_2, \beta_2)} \cdot \dotso \cdot p_k^{\min(\alpha_k, \beta_k)} </tex>. Проверим его максимальность.
Пусть существует <tex>q > p</tex>, такое что <tex>a</tex> и <tex>b</tex> делятся на <tex>q</tex>. Тогда оно необхолимо будет раскладываться на те же простые множители, что и <tex>p</tex>.
Пусть <tex dpi="140">q = p_1^{\gamma_1}\cdot p_2^{\gamma_2} \cdot \dotso \cdot p_k^{\gamma_k} </tex>. Значит, существует <tex>j \leqslant k : \min(\alpha_j, \beta_j) < \gamma_j</tex>. Из этого следует, что либо <tex>\gamma_j > \alpha_j</tex>, либо <tex>\gamma_j > \beta_j</tex>. Но в первом случае, <tex>q</tex> не окажется делителем <tex>a</tex>, а во втором {{---}} <tex>b</tex>.
}}
==Связь с наименьшим общим кратным==
<tex>\text{lcm}(a, b) = \min \left\{ d \mid d \equiv 0 \left( \bmod a\right), d \equiv 0 \left( \bmod b\right) \right\}</tex>
}}
Существует представление НОК через [[Разложение_на_множители_(факторизация) | разложение числа на простые множители]]:
{{Утверждение
|id=l002
Пусть <tex>a</tex> и <tex>b</tex> - натуральные числа. Тогда <tex dpi="140">\text{lcm}(a, b) = p_1^{\max(\alpha_1, \beta_1)}\cdot p_2^{\max(\alpha_2, \beta_2)} \cdot \dotso \cdot p_k^{\max(\alpha_k, \beta_k)}</tex>
|proof=
}}
