How Does the Euclidean Algorithm Find the GCD?

TL;DR

The Euclidean algorithm finds the greatest common divisor of two numbers by repeatedly dividing the larger number by the smaller and replacing the pair with the divisor and remainder. When the remainder (b) becomes 0, the value left in a is the GCD. For example, GCD(12, 33) equals 3.

Transcript

hello everyone welcome back in this presentation we are going to find the gcd the greatest common divisor using euclidean algorithm to find the gcd of two numbers i am going to explain you two different ways of finding the gcd in this presentation we are going to focus on method one in the next presentation we will focus on method two why waiting w... Read More

Key Insights

• The greatest common divisor (GCD) is the biggest number that divides two numbers evenly, and it is also called the highest common factor (HCF); both terms refer to the same concept.
• The manual method finds all divisors of each number, identifies the common divisors, and selects the greatest one. For GCD(12, 33), the common divisors are 1 and 3, so the answer is 3.
• A divisor of a number produces a remainder of 0 when it divides that number. The divisors of 12 are 1, 2, 3, 4, 6, and 12, giving 12 a total of six divisors.
• The GCD of two different prime numbers is always 1, because a prime number has only two factors, 1 and itself, making 1 the only shared divisor, as shown by GCD(13, 31) equals 1.
• The Euclidean algorithm simplifies finding the GCD of large numbers, avoiding the difficulty of listing every factor and comparing common divisors when numbers get big.
• Method one of the Euclidean algorithm uses four columns: quotient, a, b, and remainder. The largest number goes in a and the smaller number goes in b before dividing.
• The algorithm computes a mod b, then shifts values so b becomes the new a and the remainder becomes the new b, repeating the division until b equals 0.
• The stopping rule is that when b becomes 0, whatever value remains in a is the GCD. Division by zero is mathematically invalid, which is why the algorithm halts at that point.

Questions & Answers

Q: How do you find the GCD of two numbers using the Euclidean algorithm?

Create four columns labeled quotient, a, b, and remainder. Place the biggest of the two numbers in a and the smaller in b. Perform a mod b to get the quotient and remainder, then shift the values so b becomes the new a and the remainder becomes the new b. Repeat the division operation until the b value becomes 0. At that point, whatever number remains in a is the GCD of the two original numbers.

Q: What is the difference between GCD and HCF?

There is no difference between GCD and HCF; they are two names for the same concept. GCD stands for greatest common divisor and HCF stands for highest common factor. Whether you refer to it as GCD or HCF, the concept is identical: you are finding the biggest number, the greatest common divisor, that divides both numbers evenly. For example, 3 is both the GCD and the HCF of 12 and 33.

Q: What is the GCD of two different prime numbers?

The GCD of two different prime numbers is always 1. Prime numbers have only two factors, the number 1 and the number itself. Because two different primes share no other divisors, the only common divisor between them is 1, which is therefore the greatest common divisor. In the example, the divisors of 13 are 1 and 13, and the divisors of 31 are 1 and 31, so GCD(13, 31) equals 1.

Q: How do you find the GCD manually without the algorithm?

First find all the divisors of each number, where a divisor gives a remainder of 0 when it divides the number. Then identify the common divisors that appear in both lists. Finally, select the greatest of those common divisors. For instance, with 12 and 33, the common divisors are 1 and 3, so the greatest common divisor is 3. This method works well but becomes difficult when the numbers are large.

Q: Why does the Euclidean algorithm stop when b becomes 0?

The algorithm stops when b becomes 0 because the next step would require dividing by zero, which is mathematically invalid since numbers cannot be divided by zero. At this point no further quotient or remainder can be produced. The rule of the algorithm states that whenever the b parameter holds the value 0, whatever number remains in a is the greatest common divisor, so the process ends there with a as the answer.

Q: What is the GCD of 12 and 33?

The GCD of 12 and 33 is 3. Using the manual method, the divisors of 12 are 1, 2, 3, 4, 6, and 12, and the divisors of 33 are 1, 3, 11, and 33. The common divisors are 1 and 3, and the greatest of these is 3. This means 3 is the biggest number that can divide both 12 and 33; it divides 12 four times and 33 eleven times.

Q: How do you set up the columns for method one of the algorithm?

You create four columns because division produces two outputs and you are computing the GCD of two numbers. The columns are quotient, a, b, and remainder. Variables a and b represent the two numbers being divided, the quotient is the whole-number result of the division, and r is the remainder. Always place the biggest number in a and the smaller number in b before you begin the division operations.

Q: What is the GCD of 25 and 150?

The GCD of 25 and 150 is 25. The divisors of 25 are 1, 5, and 25, while the divisors of 150 are 1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, and 150. The common divisors shared by both numbers are 1, 5, and 25. The greatest of these common divisors is 25, so the greatest common divisor of 25 and 150 is 25.

Summary & Key Takeaways

• GCD, the greatest common divisor, is the biggest common divisor of two numbers and is also known as HCF, the highest common factor. The manual approach lists each number's divisors, finds the divisors they share, and picks the greatest, such as 3 for GCD(12, 33).

• Worked examples build the fundamentals: GCD(25, 150) is 25 since the common divisors are 1, 5, and 25, while GCD(13, 31) is 1 because two different prime numbers share only the divisor 1. Composite numbers can share several divisors.

• The Euclidean algorithm method one uses quotient, a, b, and remainder columns, placing the larger number in a. Repeatedly compute a mod b, shift the divisor and remainder into a and b, and stop when b is 0; the remaining a is the GCD.