Изменения
→Расширенный алгоритм Евклида
: <tex> a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</tex>
определена тем, что каждое <tex>r_k</tex> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
: <tex>a = bq_0 b \cdot q_0 + r_1</tex>: <tex>b = r_1q_1 r_1 \cdot q_1 + r_2</tex>: <tex>r_1 = r_2q_2 r_2 \cdot q_2 + r_3</tex>
: <tex>\cdots</tex>
: <tex>r_{k-2} = r_{k-1} \cdot q_{k-1} + r_k</tex>
: <tex>\cdots</tex>
: <tex>r_{n-1} = r_n \cdot q_n</tex>
Тогда <tex>\gcd(a, b) = r_n</tex> {{---}} последний ненулевой член этой последовательности.
}}
'''Существование''' таких <tex>r_1, r_2, ...\cdots</tex>, то есть возможность деления с остатком <tex>m</tex> на <tex>n</tex> для любого целого <tex>m</tex> и целого <tex>n\ne 0</tex>, доказывается индукцией по ''m''.
'''Корректность''' этого алгоритма вытекает из следующих двух утверждений:
|statement=
Пусть <tex>a</tex> и <tex>b</tex> — натуральные числа, тогда
* <tex>\gcd(2a2 \cdot a, 2b2 \cdot b) = 2\cdot\gcd(a, b)</tex>* <tex>\gcd(2a2 \cdot a, 2b 2 \cdot b + 1) = \gcd(a, 2b 2 \cdot b + 1)</tex>* <tex>\gcd(2a 2 \cdot a + 1, 2b 2 \cdot b + 1) = \gcd(\left|a - b\right|, 2b 2 \cdot b + 1)</tex>
|proof=
Тривиальным образом следует из определения
===Расширенный алгоритм Евклида===
В стандартном алгоритме, мы использовали следующее свойство: <tex>\gcd(a, b) = \gcd(b, a \bmod b)</tex>. Воспользуемся им для того, чтобы решить следующую задачу: найти <tex>x</tex> и <tex>y</tex> такие, что <tex>a \cdot x + b \cdot y = \gcd(a, b)</tex>. Пусть мы нашли пару <tex>x_1, y_1: \: b \cdot x_1 + (a \bmod b) \cdot y_1 = \gcd(a, b)</tex>.Очевидно, что <tex>a \bmod b = a - \lfloor \dfrac{a}{b}\rfloor \cdot b</tex>. Получаем: <tex>b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a - \lfloor \dfrac{a}{b}\rfloor \cdot b\right) \cdot y_1 = b \cdot \left(x_1 - \lfloor \dfrac{a}{b}\rfloor \cdot y_1\right) + a \cdot y_1= a \cdot y_1 + b \cdot \left(x_1 - \lfloor \dfrac{a}{b}\rfloor \cdot y_1\right)</tex>. Следовательно, приходим к расширенному алгоритму Евклида:
<font color="green">// Алгоритм возвращает тройку <tex>\gcd, x, y</tex></font>
'''function''' extendedGcd(a, b) :
'''if''' b == 0 :
'''return''' a, 1, 0, 1
gcd, <tex>x_1</tex>, <tex>y_1</tex> <tex>\leftarrow</tex> extendedGcd(b, a mod b)
x <tex>\leftarrow</tex> <tex>y_1</tex>
== Примечания==
<references />
[[Категория: Классы Теория чисел]]
==Источники информации==
* [https://en.wikipedia.org/wiki/Greatest_common_divisor Wikipedia {{---}} Greatest common divisor]
* [https://en.wikipedia.org/wiki/Binary_GCD_algorithm Wikipedia {{---}} Binary GCD Algorithm]
