you: An algorithm (as we are using the term loosely in this case) may make use of random choices. There's much literature on the subject. One can plan to make a random choice and follow that choice.
The Euclidean algorithm (for the few systems wherein it exists) is way too narrow an example. It only applies to finding a greatest common divisor of a pair of integers. It doesn't even work in many numerical systems.
There are random algorithms for arithmetic problems, though. The Miller-Rabin primality check or Dixon's factoring algorithm are examples. Random algorithms are often much faster than deterministic algorithms for the same problem. Dixon's factoring algorithm was the first sub-exponential algorithm to factor large integers.