The Euclidean algorithm is an efficient method for finding the greatest common divisor (GCD) of two integers. It is one of the oldest algorithms known, and it is still one of the most widely used algorithms for finding the GCD.
How do you find the greatest common divisor using Euclidean algorithm?
The Euclidean algorithm is based on the following principle: the GCD of two integers is the same as the GCD of their difference. This principle can be expressed mathematically as follows:
GCD(a, b) = GCD(a - b, b)
where a and b are any two integers.
The Euclidean algorithm works by repeatedly subtracting the smaller number from the larger number, until the two numbers are equal. The GCD of the two numbers is then the remainder of the last subtraction.
- Start with the two integers whose GCD you want to find.
- Divide the larger number by the smaller number.
- Set the larger number equal to the remainder from step 2, and set the smaller number equal to the original divisor.
- Repeat steps 2 and 3 until the two numbers are equal.
- The GCD of the two numbers is the remainder of the last subtraction.
Here is an example of how to use the Euclidean algorithm to find the GCD
We will calculate GCD(72, 132)
132 ÷ 72 = 1 remainder 60; replace 132 with 60:
GCD(132, 72) = GCD(72, 60)
72 ÷ 60 = 1 remainder 12; replace 72 with 12:
GCD(72, 60) = GCD(60, 12)
60 ÷ 12 = 5 remainder 0; replace 60 with 0:
GCD(60, 12) = GCD(12, 0)
The GCD is 12.
Other ways
Method 1:
Let’s find all the divisors of both numbers.
The divisors of 72 are: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72.
For instance: 72 = 1 x 72 = 2 x 36 = 3 x 24 = 4 x 18 = 6 x 12 = 8 x 9.
The divisors of 132 are: 1, 2, 3, 4, 6, 11, 12, 22, 33, 44, 66, 132.
For instance: 132 = 1 x 132 = 2 x 66 = 3 x 44 = 4 x 33 = 6 x 22 = 11 x 12.
The common divisors (present in both lists) are: 1, 2, 3, 4, 6, 12.
So, the greatest common divisor is: 12.
Note: The common divisors are the divisors of the GCD.
Method 2:
Let’s decompose the two numbers into products of prime factors.
72 = 2 x 2 x 2 x 3 x 3 = 2^3 x 3^2
132 = 2 x 2 x 3 x 11 = 2^2 x 3^1 x 11^1
To calculate the GCD, we select the common factors (present in both factorizations); if they have exponents, we take the lowest exponent; then, we multiply them:
GCD(72, 132) = 2^2 x 3^1 = 4 x 3 = 12
Method 3:
By successive subtractions.
Principle: if a < b, then: GCD(a, b) = GCD(a, b – a).
You can replace the larger of the two numbers with the difference between the two numbers; this does not change the GCD.
GCD(72, 132) = GCD(72, 132 – 72) = GCD(72, 60)
GCD(72, 60) = GCD(72 – 60, 60) = GCD(12, 60)
GCD(12, 60) = GCD(12, 60 – 12) = GCD(12, 48)
GCD(12, 48) = GCD(12, 48 – 12) = GCD(12, 36)
GCD(12, 36) = GCD(12, 36 – 12) = GCD(12, 24)
GCD(12, 24) = GCD(12, 24 – 12) = GCD(12, 12)
The GCD is 12.
If two integers have no common divisors other than 1, then their GCD is equal to 1; we say that these numbers are coprime. When you divide two integers by their GCD, you get two coprime numbers.
The GCD is often used in simplifying fractions: The best possible simplification is to divide both the numerator and the denominator by their GCD; you will directly obtain the irreducible fraction.
Greatest Common Divisor Euclidean Algorithm Worksheets
What is the greatest common divisor GCD between 128 and 96 using Euclidean algorithm?
To find the greatest common divisor (GCD) between 128 and 96 using the Euclidean algorithm
Divide the larger number by the smaller number.
– 128 ÷ 96 = 1 remainder 32
Replace the larger number with the smaller number and the smaller number with the remainder.
– New numbers: 96 (from the previous smaller number) and 32 (the remainder from step 1).
Repeat until the remainder is 0.
– 96 ÷ 32 = 3 remainder 0
The divisor at the point when the remainder becomes 0 is the GCD.
So GCD(128, 96) = 32.
What is the GCD of 75 and 45 using Euclid’s algorithm?
Divide the larger number by the smaller number.
– 75 ÷ 45 = 1 with a remainder of 30.
Replace the larger number with the smaller number and the smaller number with the remainder.
– New numbers: 45 (from the previous smaller number) and 30 (the remainder from step 1).
Repeat until the remainder is 0.
– 45 ÷ 30 = 1 with a remainder of 15.
– New numbers: 30 (from the previous smaller number) and 15 (the remainder from step 3).
– 30 ÷ 15 = 2 with a remainder of 0.
Now, the remainder is 0, so we stop.
The divisor at the point when the remainder becomes 0 is the GCD.
GCD(75, 45) = 15.
What is the GCD of 270 and 192 using Euclidean algorithm?
Divide the larger number by the smaller number.
– 270 ÷ 192 = 1 with a remainder of 78.
Replace the larger number with the smaller number and the smaller number with the remainder.
– New numbers: 192 (from the previous smaller number) and 78 (the remainder from step 1).
Repeat until the remainder is 0.
– 192 ÷ 78 = 2 with a remainder of 36.
– New numbers: 78 (from the previous smaller number) and 36 (the remainder from step 3).
– 78 ÷ 36 = 2 with a remainder of 6.
– New numbers: 36 (from the previous smaller number) and 6 (the remainder from step 3).
– 36 ÷ 6 = 6 with a remainder of 0.
Now, the remainder is 0, so we stop.
The divisor at the point when the remainder becomes 0 is the GCD.
GCD(270, 192) = 6.
What is the GCD of 2740 and 1760 using Euclidean algorithm?
What is the GCD of 24140 and 16762 using Euclid’s algorithm?
Divide the larger number by the smaller number.
– 24140 ÷ 16762 = 1 with a remainder of 7378.
Replace the larger number with the smaller number and the smaller number with the remainder.
– New numbers: 16762 (from the previous smaller number) and 7378 (the remainder from step 1).
Repeat until the remainder is 0.
– 16762 ÷ 7378 = 2 with a remainder of 2006.
– New numbers: 7378 (from the previous smaller number) and 2006 (the remainder from step 3).
– 7378 ÷ 2006 = 3 with a remainder of 1360.
– New numbers: 2006 (from the previous smaller number) and 1360 (the remainder from step 3).
– 2006 ÷ 1360 = 1 with a remainder of 646.
– New numbers: 1360 (from the previous smaller number) and 646 (the remainder from step 3).
– 1360 ÷ 646 = 2 with a remainder of 68.
– New numbers: 646 (from the previous smaller number) and 68 (the remainder from step 3).
– 646 ÷ 68 = 9 with a remainder of 10.
– New numbers: 68 (from the previous smaller number) and 10 (the remainder from step 3).
– 68 ÷ 10 = 6 with a remainder of 8.
– New numbers: 10 (from the previous smaller number) and 8 (the remainder from step 3).
– 10 ÷ 8 = 1 with a remainder of 2.
– New numbers: 8 (from the previous smaller number) and 2 (the remainder from step 3).
– 8 ÷ 2 = 4 with a remainder of 0.
Now, the remainder is 0, so we stop.
The divisor at the point when the remainder becomes 0 is the GCD.
GCD(24140, 16762) = 2.
What is the GCD of 421 and 111 by using Euclidean algorithm?
421 / 111 = 3 R 88 111 / 88 = 1 R 23 88 / 23 = 3 R 19 23 / 19 = 1 R 4 19 / 4 = 4 R 3 4 / 3 = 1 R 1 3 / 1 = 3 R 0
The GCD of 421 and 111 is the last non-zero remainder, which is 1.
What is the GCD of 1769 and 2378?
2378 / 1769 = 1 with a remainder of 609 1769 / 609 = 2 with a remainder of 551 609 / 551 = 1 with a remainder of 58 551 / 58 = 9 with a remainder of 29 58 / 29 = 2 with a remainder of 0
Therefore, the GCD of 1769 and 2378 is 29.
LEARN MATH FAST Greatest Common Divisor Euclidean Algorithm
