344
правки
Изменения
→Расширенный алгоритм Евклида
b\left(x_1 - \lfloor \frac{a}{b}\rfloor y_1\right) + a y_1</tex>. Следовательно, приходим к расширенному алгоритму Евклида:
<font color="green">// Алгоритм возвращает тройку <tex>\gcd, x, y</tex></font>
'''function''' <tex>\mathtt{extendedGcd(a, b)}:</tex> '''if''' <tex>\mathtt{b} == 0:</tex> '''return''' <tex>\mathtt{a}, 0, 1 gcd, <tex>x_1</tex> , <tex>\mathtt{gcd, x_1, y_1} </tex> <tex>\leftarrow \mathtt{</tex> extendedGcd(b, a} \bmod \mathtt{mod b)} x <tex>\leftarrow</tex> <tex>\mathtt{x} \leftarrow \mathtt{y_1}</tex> y <tex>\mathtt{y} \leftarrow \mathtt{</tex> <tex>x_1} </tex> - (\mathtt{a} \text{ div } \mathtt{b}) <tex>\cdot \mathtt{</tex> <tex>y_1}</tex> '''return''' gcd, <tex>\mathtt{gcd, x</tex>, <tex>y}</tex>
Такое представление наибольшего общего делителя называется '''соотношением Безу''', а числа <tex>x</tex> и <tex>y</tex> — '''коэффициентами Безу'''. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.
== См. также==
* [[Разложение_на_множители_(факторизация) | Разложение на множители]]
