42
правки
Изменения
→Определение
Пусть <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">a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \dotso \cdot p_k^{\alpha_k}, \:
b = q_1^{\beta_1} \cdot q_2^{\beta_2} \cdot \dotso \cdot q_k^{\beta_k}</tex>, где <tex>p_j, q_j</tex> {{---}} простые, а <tex>\alpha_j, \beta_j</tex> {{---}} натуральные
(такие разложения существуют, по [[Основная_теорема_арифметики | основной теореме арифметики]]). Без ограничения общности, можно считать, что <tex>p_j = q_j, k = n</tex> (если это не так, сделаем соответствующие <tex>\alpha</tex> и <tex>\beta</tex> равными нулю).
Очевидно, что в таком случае <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>q</tex> не существует.
}}
