 Since multiplication is not commutative, there are two versions of the Euclidean algorithm, one for right divisors and one for left divisors.Choosing the right divisors, the first step in finding the by the Euclidean algorithm can be written

where represents the quotient and the remainder.This equation shows that any common right divisor of and is likewise a common divisor of the remainder .