344
правки
Изменения
м
заменить дефисы на тире, там где должно быть тире
|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> где <tex>p_j</tex> — делитель <tex>a</tex> и <tex>b</tex>. (Если <tex>a</tex> не делится на <tex>p_j,</tex> будем считать, что <tex>p_j</tex> присутствует в разложении <tex>a</tex> в <tex>0</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}, \:
|id=l002
|statement=
Пусть <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=
Доказательство полностью аналогично доказательству [[#l001 | утверждения о НОД]], с той лишь разницей, что мы заменяем <tex>\min</tex> на <tex>\max</tex>, а знаки неравенств {{---}} на противоположные.
|proof=Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда <tex> a = t_1 k </tex> ; <tex> b = t_2 k; </tex> где <tex> t_1 </tex> и <tex> t_2 </tex> — целые числа из определения.
# Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а <tex>r = a - bq = (t_1 - t_2 q)k </tex> (выражение в скобках есть целое число, следовательно, k делит r без остатка)
# Обратное также верно и доказывается аналогично 2) - — любой делитель b и r так же является делителем a и b.
# Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.
# В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
|id=l3
|statement=
Пусть <tex>a</tex> и <tex>b</tex> - — натуральные числа, тогда
* <tex>\gcd(2a, 2b) = 2\cdot\gcd(a, b)</tex>
* <tex>\gcd(2a, 2b + 1) = \gcd(a, 2b + 1)</tex>
