153
правки
Изменения
→Расширенный алгоритм Евклида
===Расширенный алгоритм Евклида===
Формулы для <mathtex>r_i</mathtex> могут быть переписаны следующим образом:
: <mathtex>r_1 = a + b(-q_0)</mathtex>: <mathtex>r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0)</mathtex>: <mathtex>\cdots</mathtex>: <mathtex>\gcd (a,b) = r_n = as + bt</mathtex>
здесь ''s'' и ''t'' целые. Это представление наибольшего общего делителя называется '''соотношением Безу''', а числа ''s'' и ''t'' — '''коэффициентами Безу'''. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.
Отношение <tex>a/b</tex> допускает представление в виде цепной дроби:
При этом цепная дробь без последнего члена равна отношению коэффициентов Безу <tex>t/s</tex>, взятому со знаком минус:
==Наибольший общий делитель как общий делитель, делящий все остальные общие остальные общие делители==
[[Категория: Классы чисел]]
