Let’s first define the concept of GCD (Greatest Common Divisor).
DEFINITION
Common Divisors We say that d is a common divisor of two numbers, a and b, if it divides both a and b. The greatest common divisor of these two numbers is called the GCD.
The number 1 is always a common divisor of two numbers. When it is the only common divisor, we say that these two numbers are coprime.
EXAMPLE
What are the common divisors of 12 and 20?
We list all the divisors of 20: 1; 2; 4; 5; 10; and 20. We list all the divisors of 12: 1; 2; 3; 4; 6; and 12. Therefore, the numbers 12 and 20 have three common divisors: 1; 2; and 4. The GCD of these two numbers is: GCD(12; 20) = 4. So, to determine if two numbers have common divisors, do we have to list all their divisors? What if the number is 12 digits long?
No, don’t worry, there’s a simpler method for that. I’ll explain it right away!
Certainly, here’s the translation of the provided text into English:
How to Find Greatest Common Divisor Faster
The calculation method for GCD used so far is correct but requires a lot of calculations: you need to determine all the divisors for each number and then see which ones are common. We will now look at two faster methods: those based on successive subtractions and the Euclidean algorithm.
1) Method of Successive Subtractions
**Definition**
When c is a common divisor of a and b, then c is also a divisor of a – b (an accepted theorem). Therefore, when a > b, the GCD of a and b is also the GCD of a – b and b:
GCD(a, b) = GCD(a – b, b)
This gives us a new method for calculating the GCD.
**Example :**
Let’s calculate the GCD of 68 and 24:
GCD(68, 24) = GCD(68 – 24, 24) = GCD(44, 24)
GCD(44, 24) = GCD(44 – 24, 24) = GCD(20, 24)
GCD(20, 24) = GCD(20, 24 – 20) = GCD(20, 4)
GCD(20, 4) = GCD(20 – 4, 4) = GCD(16, 4)
GCD(16, 4) = GCD(16 – 4, 4) = GCD(12, 4)
GCD(12, 4) = GCD(12 – 4, 4) = GCD(8, 4)
GCD(8, 4) = GCD(8 – 4, 4) = GCD(4, 4)
GCD(4, 4) = 4 (the greatest common divisor of 4 and 4 is obviously 4)
The GCD of 68 and 24 is equal to 4.
You can also express the calculation of GCD as follows:
68 – 24 = 44
44 – 24 = 20
24 – 20 = 4
20 – 4 = 16
16 – 4 = 12
12 – 4 = 8
8 – 4 = 4
The first step is to find the difference between the two numbers for which you’re seeking the GCD. Then, you perform a series of subtractions between the two numbers, focusing on the “=” sign in each equation, so that the sign of this difference becomes positive. You stop when you obtain two identical numbers on either side of the “=” sign. In the example, this number is 4 (in bold). Consequently, the GCD of 68 and 24 is 4.
2) Method Using the Euclidean Algorithm
The Euclidean algorithm method speeds up the previous method.
**Theorem**
If a = bq + r, then GCD(a, b) = GCD(b, r).
Example :
Taking example 7 of calculating the GCD between 68 and 24:
68 = 24 × 2 + 20
24 = 20 × 1 + 4
20 = 4 × 5 + 0
The greatest common divisor is the last nonzero remainder, which is 4 (in bold).
Compared to the method of successive subtractions, you save time: there are only 3 lines of calculation instead of 7. The first two lines of the subtractive method can indeed be replaced by one: 20 is the remainder of the Euclidean division of 68 by 24.
The Greatest Common Divisor Formula
There are other several methods to calculate the greatest common divisor (GCD) of two numbers
Prime Factorization
This method involves finding the prime factors of both numbers and then identifying their common prime factors.
Formula:
GCD(a, b) = Product of common prime factors of a and b
Example:
Find the GCD of 36 and 48 using prime factorization:
Prime factors of 36 = 2^2 * 3^2
Prime factors of 48 = 2^4 * 3^1
The common prime factor is 2^2 = 4.
Division Method
This method involves dividing the larger number by the smaller number until you get a remainder of 0.
Formula:
GCD(a, b) = GCD(b, a % b)
Example:
Find the GCD of 72 and 90 using the division method:
Step 1: GCD(90, 72) = GCD(72, 18)
Step 2: GCD(72, 18) = GCD(18, 72 % 18) = GCD(18, 0)
The GCD is 18.
Listing Factors
This method involves listing all the factors of both numbers and identifying their common factors.
Formula:
GCD(a, b) = Largest common factor in the lists of factors of a and b
Example:
Find the GCD of 56 and 84 by listing factors:
Factors of 56: 1, 2, 4, 7, 8, 14, 28, 56
Factors of 84: 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84
The largest common factor is 28.
These methods provide various ways to find the greatest common divisor of two numbers, depending on the context and your preference for calculation.
Binary Algorithm (Stein’s Algorithm)
This is an efficient algorithm for finding the GCD of two numbers by using bitwise operations.
Formula:
GCD(a, b) = GCD(a/2, b/2) * 2, if both a and b are even
GCD(a, b) = GCD(a/2, b), if a is even and b is odd
GCD(a, b) = GCD(a, b/2), if a is odd and b is even
GCD(a, b) = GCD(|a – b|/2, b), if both a and b are odd
Example:
Find the GCD of 48 and 18 using Stein’s Algorithm:
Step 1: GCD(48, 18) = GCD(24, 18) * 2 (both are even)
Step 2: GCD(24, 18) = GCD(12, 18) (now only one is even)
Step 3: GCD(12, 18) = GCD(12, 9)
Step 4: GCD(12, 9) = GCD(3, 9)
Step 5: GCD(3, 9) = GCD(3, 6) * 2 (both are odd)
Step 6: GCD(3, 6) = GCD(3, 3)
Step 7: GCD(3, 3) = 3
The GCD is 3.
Greatest Common Divisor Practice Problems
A) Simplification of Fractions
Property
A fraction is irreducible when its numerator and denominator are coprime. In other words, as long as the GCD (Greatest Common Divisor) of the numerator and denominator is not equal to 1, it is possible to simplify the fraction. To simplify it to the maximum extent, you just need to divide both the numerator and the denominator by their GCD.
Example :
We want to make the following fraction irreducible:
156
24
To do this, we will calculate the GCD of the numerator and denominator, which is: GCD(156, 24).
156 = 24 × 6 + 12
24 = 12 × 2 + 0
The GCD of 156 and 24 is the last nonzero remainder, which is 12 (in bold).
To make the fraction irreducible, we divide the numerator and the denominator by 12:
156/24=(156÷12)/(24÷12)=13/2
The irreducible fraction is
13/2.
B) Problem Solving
Maximizing Resource Efficiency
Imagine you are in charge of a manufacturing plant that produces electronic gadgets. To minimize waste and maximize resource efficiency, you need to determine the ideal batch size for production. You have a limited supply of components, and you want to assemble as many gadgets as possible.
Let’s say you have 480 circuit boards and 360 sets of electronic components. Your goal is to find the largest number of gadgets you can assemble while using up all the components. This is essentially a problem of finding the greatest common divisor (GCD) of 480 and 360.
Using the Euclidean algorithm:
480 = 360 × 1 + 120 360 = 120 × 3 + 0
The greatest common divisor of 480 and 360 is the last nonzero remainder, which is 120 (in bold). So, you can produce 120 gadgets while using up all your components efficiently.
Time and Task Management
In the world of project management, efficient allocation of resources and time is essential. Let’s consider a project with two crucial tasks: Task A takes 64 hours to complete, and Task B takes 48 hours.
You need to plan the project in a way that minimizes the overall completion time. To achieve this, you want to find the greatest common divisor (GCD) of the task durations, which helps you identify the smallest unit of work that both tasks can be evenly divided into.
GCD(64, 48) can be calculated as follows:
64 = 48 × 1 + 16 48 = 16 × 3 + 0
The GCD of 64 and 48 is the last nonzero remainder, which is 16 (in bold). This means you can break down both tasks into 16-hour increments, allowing you to align them efficiently. By doing so, you optimize your project schedule and make the most of your available time and resources.
Greatest Common Divisor Worksheets
Calculate the Greatest Common Divisor (GCD) for each pair of numbers using the method you prefer. Show your work step by step.
Find the GCD of 24 and 36.
Solution:
Prime factors of 24: 2^3 * 3^1
Prime factors of 36: 2^2 * 3^2
Now, take the highest power of each prime factor:
Highest power of 2: 2^2
Highest power of 3: 3^1
Multiply these together: GCD = 2^2 * 3^1 = 4 * 3 = 12
Find the GCD of 56 and 72.
Solution:
Use the Euclidean Algorithm:
GCD(56, 72) = GCD(72, 56) = GCD(56, 16)
GCD(56, 16) = GCD(16, 8)
GCD(16, 8) = GCD(8, 0)
The GCD is 8.
Find the GCD of 75 and 90.
Solution:
Find the factors that are common to both numbers:
75 = 3 * 5 * 5 90 = 2 * 3 * 3 * 5
Multiply the common factors together:
GCD = 3 * 5 = 15
Therefore, the GCD of 75 and 90 is 15.
Find the GCD of 48 and 60.
Solution:
Use the Euclidean Algorithm:
GCD(48, 60) = GCD(60, 48) = GCD(48, 12)
GCD(48, 12) = GCD(12, 0)
The GCD is 12.
Find the GCD of 81 and 99.
Solution:
Use the Euclidean Algorithm:
GCD(81, 99) = GCD(99, 81) = GCD(81, 18)
GCD(81, 18) = GCD(18, 9)
GCD(18, 9) = GCD(9, 0)
The GCD is 9.
What is the greatest common divisor of 7469 and 2464?
Solution:
The greatest common divisor (GCD) of two numbers is the largest number that is a divisor of both numbers. To find the GCD of 7469 and 2464, we can use the Euclidean algorithm:
gcd(7469, 2464) = gcd(2464, 7469 - 3 * 2464) = gcd(2464, 77) = gcd(77, 2464 - 31 * 77) = gcd(77, 0)
Since the remainder in the last division is 0, the GCD of 7469 and 2464 is 77.
The greatest common divisor of 7469 and 2464 is 77.
What is the GCD of 826 1890?
Solution:
Use the Euclidean algorithm.
. Start by dividing the larger number by the smaller number:
GCD(826, 1890) = GCD(1890, 826)
. Now, divide 1890 by 826, and find the remainder:
1890 = 826 * 2 + 238
. Repeat the process with the smaller number and the remainder:
GCD(826, 238)
. Divide 826 by 238:
826 = 238 * 3 + 112
. Continue with the smaller number and the new remainder:
GCD(238, 112)
. Divide 238 by 112:
238 = 112 * 2 + 14
. Keep going:
GCD(112, 14)
. Divide 112 by 14:
112 = 14 * 8
. Now, you’ve reached a point where the remainder is 0. The GCD is the divisor at this step:
GCD(112, 14) = 14
So, the Greatest Common Divisor (GCD) of 826 and 1890 is 14.
What is the greatest common divisor of 1313 and 1001?
Solution:
Divide 1313 by 1001. The remainder is 312.
Divide 1001 by 312. The remainder is 77.
Divide 312 by 77. The remainder is 158.
Divide 77 by 158. The remainder is 45.
Divide 158 by 45. The remainder is 13.
Divide 45 by 13. The remainder is 0.
Therefore, the GCD of 1313 and 1001 is 13.
What is the gcd of 4655 12075?
Solution:
12075 ÷ 4655 = 2 R 2765
4655 ÷ 2765 = 1 R 1890
2765 ÷ 1890 = 1 R 875
1890 ÷ 875 = 2 R 140
875 ÷ 140 = 6 R 35
140 ÷ 35 = 4 R 0
The GCD of 4655 and 12075 is 5 × 7 = 35.
What is the greatest common divisor of 4147 and 10672
Divide 10672 by 4147. The remainder is 2378.
Divide 4147 by 2378. The remainder is 1769.
Divide 2378 by 1769. The remainder is 609.
Divide 1769 by 609. The remainder is 551.
Divide 609 by 551. The remainder is 58.
Divide 551 by 58. The remainder is 29.
Divide 58 by 29. The remainder is 0.
The non-zero remainder is 29, so the GCD of 4147 and 10672 is 29.
From Greatest Common Divisor to Arithmetic course and exercises
How to Find Greatest Common Divisor Quickly cool math art Course
