344
правки
Изменения
→Двоичный алгоритм Евклида
|statement=
Пусть <tex>a</tex> и <tex>b</tex> — натуральные числа, тогда
* <tex>\gcd(2a2\cdota, 2b) = 2\cdot\gcd(a, b)</tex>* <tex>\gcd(2a2\cdota, 2b 2\cdotb + 1) = \gcd(a, 2b 2\cdotb + 1)</tex>* <tex>\gcd(2a 2\cdota + 1, 2b 2\cdotb + 1) = \gcd(\left|a - b\right|, 2b 2\cdotb + 1)</tex>
|proof=
Тривиальным образом следует из определения
