344
правки
Изменения
→Двоичный алгоритм Евклида
|statement=
Пусть <tex>a</tex> и <tex>b</tex> — натуральные числа, тогда
* <tex>\gcd(2\cdotacdot a, 2b) = 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=
Тривиальным образом следует из определения
