Наибольший общий делитель

Материал из Викиконспекты
Версия от 15:05, 30 июня 2010; Mamoshkin.Arseny (обсуждение | вклад) (Расширенный алгоритм Евклида)
Перейти к: навигация, поиск
Эта статья находится в разработке!

Наибольший общий делитель как максимальное число, делящее два данных числа

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

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

Пусть [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]\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].

Наибольший общий делитель как общий делитель, делящий все остальные общие остальные общие делители