Наибольший общий делитель — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Связь с наименьшим общим кратным)
Строка 18: Строка 18:
  
 
==Связь с наименьшим общим кратным==
 
==Связь с наименьшим общим кратным==
 +
 +
{{Определение
 +
|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>, получаем наше утверждение
 +
}}
 +
 
==Алгоритм Евклида==
 
==Алгоритм Евклида==
  

Версия 18:57, 30 января 2017

Определение

Определение:
Наибольшим общим делителем (англ. [math]\gcd[/math]greatest common divisor) для двух целых чисел [math]m[/math] и [math]n[/math] называется наибольший из их общих делителей. Более формально, [math]\gcd(a, b) =\max \left\{ d \mid a \equiv 0 \left(\bmod d\right), b \equiv 0 \left(\bmod d\right) \right\}[/math]


Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел [math]m[/math] или [math]n[/math] не ноль.

Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел:


Определение:
Наибольший общий делитель для целочисленного множества [math]A[/math] определяется как [math]\gcd(A) = \max \left\{ d \mid \forall a_j \in A,\: a_j \equiv 0 \left(\bmod d \right)\right\}[/math]


Связь с наименьшим общим кратным

Определение:
Наименьшим общим кратным (англ. [math]\text{lcm}[/math]least common multiple) для двух чисел [math]a[/math] и [math]b[/math] называется наименьшее натуральное число, которое делится на [math]a[/math] и [math]b[/math] без остатка. Более формально [math]\text{lcm}(a, b) = \min \left\{ d \mid d \equiv 0 \left( \bmod a\right), d \equiv 0 \left( \bmod b\right) \right\}[/math]

Существует представление НОК через разложение числа на простые множители:

Утверждение:
Пусть [math]a[/math] и [math]b[/math] - натуральные числа. Тогда [math]\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)}[/math]
[math]\triangleright[/math]

Очевидно, что в таком случае [math]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)} [/math] делится на [math]a[/math] и на [math]b[/math]. Проверим его минимальность. Пусть существует [math]q \lt p[/math] — кратное [math]a[/math] и [math]b[/math]. Тогда оно необхолимо будет раскладываться на те же простые множители, что и [math]p[/math]. Пусть [math]q = p_1^{\gamma_1}\cdot p_2^{\gamma_2} \cdot \dotso \cdot p_k^{\gamma_k} [/math]. Значит, существует [math]j \leqslant k : \max(\alpha_j, \beta_j) \gt \gamma_j[/math]. Из этого следует, что либо [math]\gamma_j \lt \alpha_j[/math], либо [math]\gamma_j \lt \beta_j[/math]. Но в первом случае, [math]q[/math] окажется некратным [math]a[/math],

а во втором — [math]b[/math].
[math]\triangleleft[/math]

Наибольший общий делитель связан с наименьшим общим кратным следующим равенством:

Лемма:
Пусть [math]a[/math] и [math]b[/math] — целые числа. Тогда [math]\gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b[/math].
Доказательство:
[math]\triangleright[/math]
По утверждению о НОД и утверждению о НОК, пользуясь тем, что [math]\max(\alpha, \beta) + \min(\alpha, \beta) = \alpha + \beta[/math], получаем наше утверждение
[math]\triangleleft[/math]

Алгоритм Евклида

Стандартный алгоритм Евклида

Пусть [math]a[/math] и [math]b[/math] — целые числа, не равные одновременно нулю, и последовательность чисел

[math] a,\, b,\,r_1 \gt r_2 \gt r_3 \gt r_4 \gt \cdots \gt r_n[/math]

определена тем, что каждое [math]r_k[/math] — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

[math]a = bq_0 + r_1[/math]
[math]b = r_1q_1 + r_2[/math]
[math]r_1 = r_2q_2 + r_3[/math]
[math]\cdots[/math]
[math]r_{k-2} = r_{k-1} q_{k-1} + r_k[/math]
[math]\cdots[/math]
[math]r_{n-1} = r_n q_n[/math]

Тогда НОД(a,b), наибольший общий делитель [math]a[/math] и [math]b[/math], равен [math]r_n[/math], последнему ненулевому члену этой последовательности.

Существование таких [math]r_1, r_2, ...[/math], то есть возможность деления с остатком [math]m[/math] на [math]n[/math] для любого целого [math]m[/math] и целого [math]n\ne 0[/math], доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений:

Лемма:
Пусть [math]a = bq + r[/math], тогда [math]\gcd (a,b) = \gcd (b,r).[/math]
Доказательство:
[math]\triangleright[/math]

Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда [math] a = t_1 k [/math] ; [math] b = t_2 k; [/math] где [math] t_1 [/math] и [math] t_2 [/math] — целые числа из определения.

  1. Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а [math]r = a - bq = (t_1 - t_2 q)k [/math] (выражение в скобках есть целое число, следовательно, k делит r без остатка)
  2. Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.
  3. Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.
  4. В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
[math]\triangleleft[/math]
Лемма:
[math]\gcd (0,r) = r[/math] для любого ненулевого [math]r.[/math]

Проще сформулировать алгоритм Евклида так: если даны натуральные числа [math]a[/math] и [math]b[/math] и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.

Расширенный алгоритм Евклида

Формулы для [math]r_i[/math] могут быть переписаны следующим образом:

[math]r_1 = a + b(-q_0)[/math]
[math]r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0)[/math]
[math]\cdots[/math]
[math]\gcd (a,b) = r_n = as + bt[/math]

здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и tкоэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

Связь с цепными дробями

Отношение [math]a/b[/math] допускает представление в виде цепной дроби:

[math]\frac ab=[q_0; q_1, q_2,\cdots,q_n][/math].

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу [math]t/s[/math], взятому со знаком минус:

[math][q_0; q_1, q_2,\cdots,q_{n-1}] = -\frac ts[/math].