42
правки
Изменения
→Связь с наименьшим общим кратным
==Связь с наименьшим общим кратным==
{{Определение
|definition=
'''Наименьшим общим кратным''' (англ. <tex>\text{lcm}</tex> {{---}} ''least common multiple'') для двух чисел <tex>a</tex> и <tex>b</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
|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=
Очевидно, что в таком случае <tex dpi="140">p = 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> делится на <tex>a</tex> и на <tex>b</tex>. Проверим его минимальность.
Пусть существует <tex>q < p</tex> {{---}} кратное <tex>a</tex> и <tex>b</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 : \max(\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>.
}}
Наибольший общий делитель связан с наименьшим общим кратным следующим равенством:
{{Лемма
|id=l01
|statement=
Пусть <tex>a</tex> и <tex>b</tex> {{---}} целые числа. Тогда <tex>\gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b</tex>.
|proof=
По [[#l001 | утверждению о НОД]] и [[#l002 | утверждению о НОК]], пользуясь тем, что <tex>\max(\alpha, \beta) + \min(\alpha, \beta) = \alpha + \beta</tex>, получаем наше утверждение
}}
==Алгоритм Евклида==
