Изменения

'''Наибольшим общим делителем''' (англ. <tex>\gcd</tex> {{---}} ''greatest common divisor'') для двух целых чисел <tex>ma</tex> и <tex>nb</tex> называется наибольшее натуральное <tex>d</tex>, такое что <tex>a</tex> делится на <tex>d</tex> и <tex>b</tex> делится на <tex>d</tex>. Более формально,

Пусть <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>-ой степени.)

Пусть <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>

  <font color=green"darkgreen">// <tex>p</tex> {{---}} множество простых чисел в разложении <tex>a</tex></font> <font color=green>// <tex>q</tex> {{---}} множество простых чисел в разложении <tex>b</tex></font> <font color=green>// <tex>\alpha</tex> {{---}} степени простых чисел в разложении <tex>a</tex></font> <font color=green>// <tex>\beta</tex> {{---}} степени простых чисел в разложении <tex>b</tex></font> '''function''' <tex>\mathtt{naiveGcd}(p, q, <tex>\alpha</tex>, <tex>\beta):</tex>): gcd <tex>\mathtt{gcd} \leftarrow 1</tex>1 i, j <tex>\mathtt{i, j} \leftarrow 0, 0</tex>0, 0 '''while''' <tex>\mathtt{i} < p\mathtt{.length()}</tex> '''and''' <tex>\mathtt{j} < q\mathtt{.length()}:</tex> '''if''' <tex>p_i</tex> == <tex> q_j:</tex>: t <tex>\mathtt{t} \leftarrow \</tex> min(<tex>\alpha_i</tex>, <tex>\beta_j)beta_i</tex>) gcd = gcd <tex>\mathtt{gcd} = \mathtt{gcd} \cdot </tex> <tex>p_i^{\mathtt{t}}</tex> '''else if''' <tex>p_i < /tex> < <tex>q_j:</tex>: <tex>\mathtt{i} \mathrel{+}\mathrel{\mkern-2mu}= 1</tex>

<tex>\mathtt{j} \mathrel{+}\mathrel{\mkern-2mu}= 1</tex> '''return''' <tex>\mathtt{gcd}</tex>

: <tex>a = bq_0 b \cdot q_0 + r_1</tex>: <tex>b = r_1q_1 r_1 \cdot q_1 + r_2</tex>: <tex>r_1 = r_2q_2 r_2 \cdot q_2 + r_3</tex>

: <tex>r_{k-2} = r_{k-1} \cdot q_{k-1} + r_k</tex>

: <tex>r_{n-1} = r_n \cdot q_n</tex>

Тогда <tex>\gcd(a, b) = r_n</tex> {{---}} последнему ненулевому члену последний ненулевой член этой последовательности.

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

|statement=Пусть <tex>a = bq b\cdot q + r</tex>, тогда <tex>\gcd (a,b) = \gcd (b,r).</tex>|proof=# Пусть <tex> k </tex> — любой общий делитель чисел <tex> a </tex> и <tex> b</tex>, не обязательно максимальный, тогда <tex> a = t_1 \cdot k </tex> ; <tex> b = t_2 \cdot k; </tex> ; где <tex> t_1 </tex> и <tex> t_2 </tex> — целые числа из определения.# Тогда <tex> k </tex> также общий делитель чисел <tex> b </tex> и <tex> r</tex>, так как <tex> b </tex> делится на <tex> k </tex> по определению, а <tex>r = a - bq b \cdot q = (t_1 - t_2 \cdot q)\cdot k </tex> (выражение в скобках есть целое число, следовательно, <tex> k </tex> делит <tex> r </tex> без остатка)# Обратное также верно и доказывается аналогично 2) - : пусть <tex> k </tex> — любой общий делитель чисел <tex> b </tex> и <tex> r </tex>, не обязательно максимальный, тогда <tex> b = t_1 \cdot k </tex> ; <tex> r = t_2 \cdot k </tex>; где <tex> t_1 </tex> и <tex> t_2 </tex> — целые числа из определения.# Тогда <tex> k </tex> также общий делитель чисел <tex> a </tex> и <tex> b </tex>, так же является делителем как <tex> b </tex> делится на <tex> k </tex> по определению, а <tex>a и = b.\cdot q + r = (t_1 \cdot q + t_2)\cdot k </tex> (выражение в скобках есть целое число, следовательно, <tex> a </tex> делит <tex> a </tex> без остатка)# Следовательно, все общие делители пар чисел <tex> a</tex>,<tex> b </tex> и <tex> b</tex>,<tex> r </tex> совпадают. Другими словами, нет общего делителя у чисел <tex> a</tex>,<tex> b</tex>, который не был бы также делителем <tex> b</tex>,<tex> r</tex>, и наоборот.

'''function''' <tex>\mathtt{euclideanGcd}(\mathtt{a, b}):</tex> '''while''' b <tex>\mathtt{b} \neq 0:</tex>0 : t <tex>\mathtt{t} \leftarrow \mathtt{b}</tex>b b <tex>\mathtt{b} \leftarrow \mathtt{a} \bmod \mathtt{b}</tex>a mod b a <tex>\mathtt{a} \leftarrow \mathtt{t}</tex>t '''return''' <tex>\mathtt{a}</tex>

Пусть <tex>a</tex> и <tex>b</tex> - — натуральные числа, тогда* <tex>\gcd(2a2 \cdot a, 2b2 \cdot b) = 2\cdot\gcd(a, b)</tex>* <tex>\gcd(2a2 \cdot a, 2 \cdot b + 1) = \gcd(a, 2 \cdot b + 1)</tex>* <tex>\gcd(2 \cdot a + 1, 2b 2 \cdot b + 1) = \gcd(\left|a- b\right|, 2b 2 \cdot b + 1)</tex>

Пользуясь этим, и утверждением [[#l2 | о НОДе нуля]], определим двоичный алгоритм Евклида(ниже будет дана рекурсивная реализация, для лучшей читаемости): '''function''' binaryGcd(a, b) : '''if''' a == b '''or''' b == 0 : '''return''' a '''if''' a == 0 : '''return''' b <font color="darkgreen">// первые два случая</font> '''if''' a mod 2 = 0 : '''if''' b mod 2 = 0 : '''return''' binaryGcd(a / 2, b / 2) <tex>\cdot</tex> 2 '''else''' '''return''' binaryGcd(a / 2, b) <font color="darkgreen">// второй случай, только <tex>a</tex> и <tex>b</tex> поменяли местами</font> '''if''' b mod 2 = 0 : '''return''' binaryGcd(a, b / 2) <font color="darkgreen">// остается третий случай. На самом деле, мы можем оставлять справа и <tex>a</tex>, и <tex>b</tex> // поэтому давайте всегда оставлять меньшее</font> '''if''' a > b : '''return''' binaryGcd((a - b) / 2, b) '''return''' binaryGcd((b - a) / 2, a)

Формулы для Можно показать<texref>r_ihttp://maths-people.anu.edu.au/~brent/pd/rpb183pr.pdf Twenty years' analysis of the Binary Euclidean Algorithm</texref> могут быть переписаны следующим образом:, что этот алгоритм, в среднем на 60% более эффективен, чем классический.

===Расширенный алгоритм Евклида===В стандартном алгоритме мы использовали следующее свойство: <tex>\gcd(a, b) = \gcd(b, a \bmod b)</tex>. Воспользуемся им для того, чтобы решить следующую задачу: найти <tex>x</tex> и <tex>y</tex>r_1 такие, что <tex>a \cdot x + b \cdot y = \gcd(a , b)</tex>. Пусть мы нашли пару <tex>x_1, y_1: \: b \cdot x_1 + (a \bmod b) \cdot y_1 = \gcd(-q_0a, b)</tex>.Очевидно, что <tex>a \bmod b = a - \lfloor \dfrac{a}{b}\rfloor \cdot b</tex>. Получаем: <tex>r_2b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a - r_1q_1 \lfloor \dfrac{a}{b}\rfloor \cdot b\right) \cdot y_1 = ab \cdot \left(x_1 -q_1\lfloor \dfrac{a}{b}\rfloor \cdot y_1\right)+ a \cdot y_1 = a \cdot y_1 +b\cdot \left(1+q_1q_0x_1 - \lfloor \dfrac{a}{b}\rfloor \cdot y_1\right)</tex>. Следовательно, приходим к расширенному алгоритму Евклида: <font color="green">// Алгоритм возвращает тройку <tex>\gcd, x, y</tex></font> '''function''' extendedGcd(a, b) : '''if''' b == 0 : '''return''' a, 1, 0 gcd, <tex>x_1</tex>, <tex>y_1</tex> <tex>\leftarrow</tex> extendedGcd(b, a mod b) x <tex>\cdotsleftarrow</tex> <tex>y_1</tex>: y <tex>\gcd leftarrow</tex> <tex>x_1</tex> - (a,div b) = r_n = as + bt<tex>\cdot</tex> <tex>y_1</tex>здесь ''s'return' и ''t'' целые. Это gcd, <tex>x</tex>, <tex>y</tex>Такое представление наибольшего общего делителя называется '''соотношением Безу''', а числа ''s'' <tex>x</tex> и ''t'' <tex>y</tex> — '''коэффициентами Безу'''. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

==== Связь с цепными дробями ==См. также==* [[Разложение_на_множители_(факторизация) | Разложение на множители]]Отношение <tex>a/b</tex> допускает представление в виде цепной дроби:: <tex>\frac ab=* [[q_0; q_1, q_2,\cdots,q_nПростые_числа | Простые числа]]</tex>. При этом цепная дробь без последнего члена равна отношению коэффициентов Безу <tex>t/s</tex>, взятому со знаком минус:: <tex>* [[q_0; q_1, q_2,\cdots,q_{n-1}Основная_теорема_арифметики | Основная теорема арифметики]] = -\frac ts</tex>.

[[Категория: Классы Теория чисел]] ==Источники информации==* [https://en.wikipedia.org/wiki/Greatest_common_divisor Wikipedia {{---}} Greatest common divisor]* [https://en.wikipedia.org/wiki/Binary_GCD_algorithm Wikipedia {{---}} Binary GCD Algorithm]