В основе бинарного алгоритма лежат следующие простые замечания:
1) Если а и b — четные числа, то НОД(а,b) = 2НОД(а/2,b/2).
2) Если а — четно,а b — нечетно, то НОД(а,b) = НОД(а/2,b).
3) Если а — нечетно,а b — четно, то НОД(а,b) = НОД(а,b/2).
4) Если а и b — нечетные числа, то НОД(а,b) = НОД((a-b)/2,b).
5) Если b = 0, то НОД(а,b) = а.
Приведем теперь описание бинарного алгоритма.
d:=1 {d — наибольший общий делитель а и b}
while b > 0 do begin
if а < b
then begin с:=а;а:=b;b:=с;end;
If (a — четное)
Then if (b — четное)
then begin a:=а/2; b:=b/2; d=2d;end
else a:=а/2
Else if (b — четное)
then b:=b/2
else а:=(а-b)/2;
end;
d:=d а;
End.
Если основание системы счисления равно 2, либо степени 2, то операция деления на 2 и умножения на 2 сводятся к сдвигу и выполняются особенно быстро. На каждой итерации бинарного алгоритма либо число а, либо число b уменьшается, по крайней мере, в два раза. Общее число итераций алгоритма, отсюда, ограничено сверху величиной 
. С другой стороны, полученная верхняя оценка не может быть существенно понижена. Действительно, если 
, 
, то число итерации бинарного алгоритма равно k+j-1.
Трудоемкость одной итерации бинарного алгоритма не более O(n). Поскольку b<а<рn, то число итераций не более O(n), а, следовательно, общая трудоемкость бинарного алгоритма — 
.
Тем самым доказана
Теорема. Трудоемкость бинарного алгоритма — .
