748
правок
Изменения
→Стандартный алгоритм Евклида
Тогда <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(2\cdotacdot a, 2b2 \cdot b) = 2\cdot\gcd(a, b)</tex>* <tex>\gcd(2\cdotacdot a, 2\cdotb cdot b + 1) = \gcd(a, 2\cdotb cdot b + 1)</tex>* <tex>\gcd(2\cdota cdot a + 1, 2\cdotb cdot b + 1) = \gcd(\left|a - b\right|, 2\cdotb cdot b + 1)</tex>
|proof=
Тривиальным образом следует из определения
