Изменения

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