Primitive roots and the Euclidean algorithm