153
правки
Изменения
→Расширенный алгоритм Евклида
===Расширенный алгоритм Евклида===
Формулы для <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>.
==Наибольший общий делитель как общий делитель, делящий все остальные общие остальные общие делители==
[[Категория: Классы чисел]]
