42
правки
Изменения
→Двоичный алгоритм Евклида
'''return''' <tex>\mathtt{binaryGcd((b - a)\: /\: 2, a)}</tex>
Корректность данного алгоритма следует из того, что он на каждом шаге делает эквивалентные преобразования НОД(это следует из утверждений [[#l3 | о НОДе четных и нечетных]] и [[#l2 | о НОДе нуля]]).
===Расширенный алгоритм Евклида===
