The greatest common divisor is the largest possible positive integer that can divide both input integers with no remainder. The greatest common divisor has a few solving methods that allow it to be computed by hand, the most popular method is known as Euclid's Algorithm. Below we will dive into Euclid's Algorithm!
When trying to find the greatest common divisor (GCD) of two numbers, a and b we can use Euclid's Algorithm. The rules of Euclid's Algorithm are as followed:These steps are can seem complicated, so let's see them in action to get a better grasp of what is going on. For example, we can try to find the GCD of 45 and 117.To start, neither number is 0. To do the next step we need to put our numbers into "quotient remainder form." To do this, pick the larger of the two numbers, and make that number a. The smaller number becomes b. In this case, our a is 117 and our b is 45.The q and r are the quotient, the whole result of 117 divided by 45, and the remainder of that division. 117/45 is 2 with a remainder of 27. For help doing remainder division, check out our modulo tool. Plug the two numbers in to complete our quotient remainder equation.As our algorithm outlines, since neither our a or b is 0, we need to select a new pair of numbers to continue searching for the GCD. From our equation, the new a will be our old b 45, and our new b will be the remainder, 27.Neither number is 0, so we construct the quotient remainder equation again.Neither number is 0, so we continue again with 27 as our a and 18 as our b.Neither number is 0, so we continue one last time with 18 as our a and 9 as our b.Let's extract our a and b as if we were continuing the process once more. If we do, we get 9 as our a and 0 as our b. Since one of the numbers is 0, the other is the GCD. Therefore, the GCD of 117 and 45 is 9!
Our a is 6 and b is 2. Since r = 0, 2 is the GCD of 2 and 6.Our a is 20 and b is 7.Neither number is 0, so try again with 7 and 6 as the new a and b.Neither number is 0, so try again with 6 and 1 as the new a and b.Since r = 0, 1 is the GCD of 7 and 20.Our a is 20 and b is 20.Since r = 0, 20 is the GCD of 20 and 20.Since one of the numbers is already 0, the other is the GCD.Our a is 323 and b is 136.Neither number is 0, so try again with 136 and 51 as the new a and b.Neither number is 0, so try again with 51 and 34 as the new a and b.Neither number is 0, so try again with 34 and 17 as the new a and b.Since r = 0, 17 is the GCD of 323 and 136.
Watch detailed video tutorials about Greatest Common Divisor (GCD) !
GCD - Euclidean Algorithm (Method 1)
15 minutes
How to Find the Greatest Common Divisor
4 minutes
On Demand Computer Science Theory Education for Students.