“Finding the greatest common divisor (GCD) of two positive integers results in the time complexity…

The GCD (by Euclid's algorithm) is found by repeatedly replacing the larger number with the remainder of dividing it by the smaller one. Each such step reduces the larger number to less than half its previous value within at most two steps, so the number of steps needed is proportional to $\log N$, giving a time complexity of $O(\log N)$.