Euclid's Method

We have seen how to calculate $GCD$ (or $HCF$) using the factorisation method. Now let us try to use this method to find the GCD of two large numbers. Let us take $1961$ and $2257$. You will find that the factoring large numbers such as these, take a lot of time and calculation. Luckily for us, there is a much easier and faster way of finding the $GCD$ of two numbers, without factoring them. This method was invented by a Greek mathematician named Euclid in around 300 BCE.

The steps of this method are as follows:

1. Take the larger number as the dividend and the smaller number as divisor.

2. Divide the dividend with the divisor.

3. If the remainder is $0$, then the divisor is the $GCD$. Stop here.

4. If the remainder is not $0$, replace the previous dividend with the divisor and the previous divisor with the remainder.

5. Go back to step 2, with the new dividend and the divisor.

Let us try this with our example with $1961$ and $2257$.

Our first dividend is $2257$ and the divisor is $1961$.

$\begin{array}{rl} \phantom{000}1 \\[-5pt]1961 \enclose{longdiv}{2257} \\ \underline{1961} \\ 296 & \Leftarrow & \hbox{The remainder is 296}\end{array}$

So, our new dividend is $1961$ and divisor is $296$

$\begin{array}{rl}\phantom{000}6 \\[-5pt]296 \enclose{longdiv}{1961} \\ \underline{1776} \\ 185 & \Leftarrow & \hbox{The remainder is 185}\end{array}$

-----------book page break-----------

Our next dividend is $296$ and divisor is $185$.

$\begin{array}{rl}\phantom{00}1 \\[-5pt]185 \enclose{longdiv}{296} \\ \underline{185} \\ 111 & \Leftarrow & \hbox{The remainder is 111}\end{array}$

Our next dividend is $185$ and divisor is $111$.

$\begin{array}{rl}\phantom{00}1 \\[-5pt]111 \enclose{longdiv}{185} \\ \underline{111} \\ \phantom{0}74 & \Leftarrow & \hbox{The remainder is 74}\end{array}$

Our next dividend is $74$ and divisor is $37$.

$\begin{array}{rl}\phantom{0}2 \\[-5pt]37 \enclose{longdiv}{74} \\ \underline{74} \\ \phantom{0}0 & \Leftarrow & \hbox{The remainder is 0}\end{array}$

Here we see that the remainder is $0$, so the divisor is our GCD, which is $37$.

As an interesting side note, sometimes computers need to calculate GCD of numbers as large as 600 digit numbers. If they used the factoring method, it could take more than thousands of years, even for the fastest computer in the world, to just factorize these numbers. Computers use the Euclid's method to calculate GCDs of these numbers.

You can try the speed-practice widget in the next page to enhance your skill with this method.

-----------book page break-----------

Try the following widget to practice to improve your speed and skill.