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