42
правки
Изменения
→Двоичный алгоритм Евклида
* <tex>\gcd(2a, 2b) = 2\cdot\gcd(a, b)</tex>
* <tex>\gcd(2a, 2b + 1) = \gcd(a, 2b + 1)</tex>
* <tex>\gcd(2a + 1, 2b + 1) = \gcd(\left|a - b\right|, 2b + 1)</tex>
|proof=
Тривиальным образом следует из определения
}}
Пользуясь этим, и утверждением [[#l2 | о НОДе нуля]], определим двоичный алгоритм Евклида(ниже будет дана рекурсивная реализация, для лучшей читаемости):
===Расширенный алгоритм Евклида===
