The Euclidean algorithm is a computational process that computes the GCD of two positive integers. It uses remainders to find the greatest common divisor between the two numbers.
First let's look at the process of long division. Take two positive integers, \(a\) and \(b\) such that \(a>b\). Euclidean division is a process to write \(a\) and \(b\) in the form
\[a=qb+r\]
where \(q\) is a positive integer called the quotient, and \(0\leq r<b\) is called the remainder.
Let's look at a quick example of long division.
Taking the integers \(44\) and \(17\) and performing long division gives
$$\begin{array}{r}2\phantom{)} \\ 17{\overline{\smash{\big)}\,44\phantom{)}}}\\ \underline{-~\phantom{(}0\phantom{-b)}}\\ 44\phantom{)}\\ \underline{-~\phantom{()}34}\\ 10\phantom{)} \end{array}$$
Therefore, 44 divided by 17 gives the quotient 2 with remainder 10.
So let \(a=44\) and \(b=17\), then substituting into the formula gives
\[\begin{align} a&=qb+r \\ 44&=2\cdot17+10. \end{align}\]
Steps of the Euclidean Algorithm
Take two positive integers, \(a\) and \(b\) such that \(a>b\). To compute the \(\text{GCD} (a,b)\), the steps of the Euclidean Algorithm are:
Step 1: Divide \(a\) by \(b\) so that \(a=bq_1+r_1\) where \(r_1\) is the remainder when \(b\) is divided by \(a\). Then
\[\text{GCD} (a,b)=\text{GCD} (b,r_1) .\]
Step 2: Since \(b>r_1\), divide \(b\) by \(r_1\) so that \(b=r_1q_2+r_2\). Then
\[\text{GCD} (b,r_1)=\text{GCD} (r_1,r_2).\]
Step 3: Since \(r_1>r_2\), you know that \(r_1=r_2q_3+r_3\). That means
\[\text{GCD} (r_1, r_2)=\text{GCD} (r_2, r_3).\]
Step 4: Repeat this for the remainders until \(r_k=0\).
Step 5: Then you have
\[\begin{align} \text{GCD} (a,b)&=\text{GCD} (b,r_1) \\ &=\text{GCD} (r_1, r_2) \\ &=\vdots \\ &=\text{GCD} (r_{k-1}, r_k) \\ &=\text{GCD} (r_{k-1},0) \\ &=r_{k-1} . \end{align}\]
Therefore, the GCD is the last non-zero remainder of the Euclidean division. Of course, the best way to understand this is with some examples.
Greatest Common Divisor Examples
Let's start with one where you know that the answer is supposed to be \(1\), so you can see that the Euclidean Algorithm works.
Use the Euclidean Algorithm to find the GCD of \(44\) and \(17\).
Answer:
Step 1: Since \(44>17\), divide \(44\) by \(17\) so that \(44=17\cdot 2+10\) where \(10\) is the remainder when \(44\) is divided by \(17\). Then
\[\text{GCD} (44,17)=\text{GCD} (17,10) .\]
Step 2: Now divide \(17\) by \(10\) so that \(17=1 \cdot 10+7\). So
\[\text{GCD} (17,10)=\text{GCD} (10,7).\]
Step 3: Now \(10=1\cdot 7+3\), so
\[\text{GCD} (10,7)=\text{GCD} (7,3) .\]
Step 4: Here \(7=2\cdot 3+1\), so
\[\text{GCD} (7, 3)=\text{GCD} (3, 1).\]
Step 5: In this step, \( 3=1\cdot 3\) with no remainder. Therefore, \(\text{GCD} (44,17)=1\).
Let's take a look at another example.
Find the GCD of \(12\) and \(30\) using the Euclidean Algorithm.
Answer:
Since \(30 > 12\), \(a=30\) and \(b=12\) in the Euclidean Algorithm.
Step 1: You now have to write \(a\) in the form \(a=bq+r\), which gives you \(30=(12\cdot 2)+6\).
You know that \(\text{GCD} (a, b) =\text{GCD} (b, r)\), so
\[\text{GCD} (30, 12) = \text{GCD} (12, 6).\]
Step 2: Now, let \(b=12\) and \(r_1=6\) and carry out the same process again. That means \(12=(6\cdot 2)+0\).
Now \(r_1=6\) and \(r_2=0\), so
\[\text{GCD} (r_1,r_2)=\text{GCD} (6,0)=6 .\]
Step 4: Wait, the algorithm ends as soon as you get a remainder of \(0\), which you already have! That means you get to skip Step 4.
Step 5: Now you know that
\[ \begin{align} \text{GCD} (6,0) &=\text{GCD} (12,6) \\ &=\text{GCD} (30,12) \\ &=6 . \end{align}\]
Therefore the GCD of \(30\) and \(12\) is \(6\).
Explanations 
Exams 
Magazine 
