Изменения

: <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>r_{k-2} = r_{k-1} \cdot q_{k-1} + r_k</tex>

: <tex>r_{n-1} = r_n \cdot q_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 = bq b\cdot q + r</tex>, тогда <tex>\gcd (a,b) = \gcd (b,r).</tex>|proof=# Пусть <tex> k </tex> — любой общий делитель чисел <tex> a </tex> и <tex> b </tex>, не обязательно максимальный, тогда <tex> a = t_1 \cdot k </tex> ; <tex> b = t_2 \cdot k; </tex> ; где <tex> t_1 </tex> и <tex> t_2 </tex> — целые числа из определения.# Тогда <tex> k </tex> также общий делитель чисел <tex> b </tex> и <tex> r </tex>, так как <tex> b </tex> делится на <tex> k </tex> по определению, а <tex>r = a - bq b \cdot q = (t_1 - t_2 \cdot q)\cdot k </tex> (выражение в скобках есть целое число, следовательно, <tex> k </tex> делит <tex> r </tex> без остатка)# Обратное также верно и доказывается аналогично 2) : пусть <tex> k </tex> — любой общий делитель чисел <tex> b </tex> и <tex> r </tex> так же является делителем , не обязательно максимальный, тогда <tex> b = t_1 \cdot k </tex> ; <tex> r = t_2 \cdot k </tex>; где <tex> t_1 </tex> и <tex> t_2 </tex> — целые числа из определения.# Тогда <tex> k </tex> также общий делитель чисел <tex> a </tex> и <tex> b </tex>., так как <tex> b </tex> делится на <tex> k </tex> по определению, а <tex>a = b \cdot q + r = (t_1 \cdot q + t_2)\cdot k </tex> (выражение в скобках есть целое число, следовательно, <tex> a </tex> делит <tex> a </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>

В стандартном алгоритме, мы использовали следующее свойство: <tex>\gcd(a, b) = \gcd(b, a \bmod b)</tex>. Воспользуемся им для того, чтобы решить следующую задачу: найти <tex>x</tex> и <tex>y</tex> такие, что <tex>ax a \cdot x + by b \cdot y = \gcd(a, b)</tex>. Пусть мы нашли пару <tex>x_1, y_1: \: bx_1 b \cdot x_1 + (a \bmod b)\cdot y_1 = \gcd(a, b)</tex>.Очевидно, что <tex>a \bmod b = a - \lfloor \fracdfrac{a}{b}\rfloor \cdot b</tex>. Получаем: <tex>bx_1 b \cdot x_1 + (a \bmod b)\cdot y_1 = b \cdot x_1 + \left(a - \lfloor \fracdfrac{a}{b}\rfloor \cdot b\right)\cdot y_1 = b\cdot \left(x_1 - \lfloor \fracdfrac{a}{b}\rfloor \cdot y_1\right) + a \cdot y_1</tex>. Следовательно, приходим к расширенному алгоритму Евклида:

[[Категория: Классы Теория чисел]]