Идея алгоритма состоит в том, что мы пытаемся «исчерпать» меньшей величиной (пускай это будет число b) большую – меньшая, скорее всего, уложится в большей некоторое целое число раз с каким-то остатком, величина которого строго меньше той величины, которой мы черпали. Ну это и понятно – если бы она была «нестрого меньше», то мы смогли бы ее зачерпнуть еще один полный раз. Затем мы уменьшаем «кандидата» на общую меру, черпая теперь уже величиной остатка. Поскольку оба числа у нас по условию целые, то в худшем случае такой общей мерой будет единица – тогда говорят, что числа a и b взаимно просты, или что НОД (a, b) = 1 – иначе НОД (a, b) будет равен последнему ненулевому остатку в организованной таким образом процедуре.