Euclidean Algorithm

The Euclidean algorithm is a method to find the greatest common divisor of two positive integers, a and b, where a > b. We can denote the greatest common divisor of a and b as gcd(a,b)

The Euclidean algorithm is based on the following:

• If a and b are positive integers, there exist integers unique non-negative integers q and r so that a = bq + r , where r < b.

•  \(a = bq + r \rightarrow gcd(a,b) = gcd(b,r)\)

• gcd(z,0) = z, for any integer.

Algorithm steps:

1. Express a in the form a = bq+ r.
2. End if r = 0 and report b as the gcd. Otherwise b becomes our new a and r becomes our new b and repeat step 1.

Let's find the greatest common divisor of 732 and 345 using the Euclidean algorithm.

\begin{align*}
732 &= 345(2) + 42
\\345 &= 42(8) + 9
\\42 &= 9(4) + 6
\\9 &= 6(1) + 3
\\6 &= 3(2) + 0
\end{align*}

From above it follows that gcd(732,345) = gcd(345,42) = gcd(42,9) = gcd(9,6) = gcd(6,3) = gcd(3,0) = 3.


A common mistake is to report that the gcd(a,b) is the quotient, q, in the final line. In this case some might erroneously report gcd(732, 345) = 2. It helps to remember the second point above to avoid committing this mistake. The gcd is the last non-zero remainder.