Explanations 
Flashcards 
StudySmarter IA 
Notes 
Study Plans 
Study Sets 
Exams 
Magazine 
Find a job 
Mobile App 
Jump to a key chapter
You can use the concept of the greatest common divisor to solve this because you are dividing the lengths of rope into smaller pieces (factors) of \(48\) and \(32\), and you are looking for the longest (greatest) possible length that is common to both original pieces. So, since the greatest common divisor of \(48\) and \(32\) is \(1\), you should cut each piece to be \(12\) inches long.
Here you are using the concept of the greatest common divisor to split something into smaller sections. There are many other applications of the greatest common divisor and this article will explain what the greatest common divisor is and two different methods of finding it.
Meaning of the Greatest Common Divisor
So what is a greatest common divisor anyway?
The greatest common divisor of a group of integers, often abbreviated to GCD, is defined as the greatest possible natural number which divides the given numbers with zero as the remainder.
To cover the case when both of your integers is zero, \(\text{GCD}(0, 0)\) is defined to be \(0\).
The greatest common divisor has many practical applications ranging from Simplifying Fractions and number theory to encryption algorithms.
The greatest common divisor (GCD) is also called the greatest common factor (GCF) or the highest common factor (HCF).
Let's take a look at a quick example.
What is \( \text{GCD}(4, 12)\)?
Answer:
The GCD of \(4\) and \(12\) is \(4\), since \(4\) is the largest natural number that divides \(4\) and \(12\) at the same time.
One more quick example.
What is \(\text{GCD}(-36, 16)\)?
Answer:
You know that the divisors of \(-36\) are \(\pm 36, \pm 18, \pm 9, \pm 3, \pm 2, \pm 1\). The divisors of \(16\) are \(16, 8, 4, 2, 1\). Remember that when you are choosing the GCD you always take the largest natural number that divides both, so the GCD is always a positive number. Looking at the lists of divisors, you can then see that \(\text{GCD}(-36, 16) = 2\).
What kinds of things are true about the GCD?
Greatest Common Divisor Rules
For integers \(a, b\) and \(c\), the GCD has the following properties:
Identity Property: \(\text{GCD} (a,0)=|a|\).
The Commutative Property: \(\text{GCD} (a,b)=\text{GCD} (b,a)\).
The Associative Property: \(\text{GCD} (a, \text{GCD} (b, c)) = \text{GCD} (\text{GCD} (a, b),c)\).
The Distributive Property: \(\text{GCD} (ab, ac) =a \text{GCD} (b,c)\).
Let's look at an example that applies the properties.
Find the following:
(a) \(\text{GCD} (-4,0) \)
(b) \(\text{GCD} (10, 24, 35) \)
(c) \(\text{GCD} ( 24, 36) \)
Answer:
(a) Using the Identity Property and the Commutative Property,
\[\begin{align} \text{GCD} (-4,0)&=\text{GCD} (0,-4)\\ &=|-4| \\ &=4 .\end{align}\]
(b) Let's use the Associate Property, which tells you that
\[ \begin{align} \text{GCD} (10, 24, 35) &= \text{GCD} (10, \text{GCD} (24, 35)) \\ &= \text{GCD} (\text{GCD} (10, 24),35).\end{align} \]
Starting with the one that looks the easiest, \( \text{GCD} (24, 35) = 1\). So
\[ \begin{align} \text{GCD} (10, 24, 35) &= \text{GCD} (10, \text{GCD} (24, 35)) \\ &= \text{GCD} (1,24).\\ &= 24. \end{align} \]
(c) This is a good place to use the Distributive Property, since both \(24\) and \(36\) are divisible by \(2\). That means
\[ \begin{align} \text{GCD} (24, 36) &= \text{GCD} (2\cdot 12, 2\cdot 18) \\ &= 2\cdot \text{GCD} (12, 18). \end{align} \]
You know that both \(12\) and \(18\) are divisible by \(2\), so you can use the Distributive Property again to get
\[ \begin{align} \text{GCD} (24, 36) &= 2\cdot \text{GCD} (12, 18) \\ &= 2\cdot \text{GCD} (2\cdot 6, 2\cdot 9)\\ &= 2\cdot 2 \cdot \text{GCD} (6, 9) \\ &= 4\cdot \text{GCD} (6, 9) .\end{align} \]
But now \(3\) divides both \(6\) and \(9\), so you can use the Distributive Property one more time to get
\[ \begin{align} \text{GCD} (24, 36) &= 4 \cdot \text{GCD} (6, 9) \\ &= 4\cdot \text{GCD} (3\cdot 2, 3\cdot 3)\\ &= 4\cdot 3 \cdot \text{GCD} (2, 3) \\ &= 12\cdot \text{GCD} (2, 3) .\end{align} \]
Since \(\text{GCD} (2, 3) = 1 \) you can now say that
\[ \text{GCD} (24, 36) = 12.\]
Notice that before you can find the GCD, you need to know what divisors (or factors) the numbers have, especially what common divisors they have. Remember that a factor of a number \(a\) is a number \(b\) that divides into \(a\) with no remainder.
There are two main ways to find the Greatest Common Divisor (GCD):
finding all common divisors (also called the common factor method); and
using the Euclidean algorithm.
The Common Factor Method
For this method, you use inspection to write out all the divisors or factors of the numbers given choose the largest one. This will be your greatest common divisor. This is easiest to see using an example.
Suppose we want to find the GCD of \(12, 46\) and \(78\).
Answer:
By inspection, you can list all the factors of the three numbers:
- The factors of \(12\) are \(1, 2, 3, 4, 6, 12\).
- The factors of \(46\) are \(1, 2, 23, 46\).
- The factors of \(78\) are \(1, 2, 3, 6, 13, 26, 39, 78\).
Since the largest number that appears on all three lists is \(2\), you would write \(\text{GCD} (12,46,78)=2\).
Let's take a look at another example.
Find the greatest common divisor of \(15\) and \(36\).
Answer:
You can start by writing out all the divisors of both \(15\) and \(36\):
- The divisors of \(15\) are \(1, 3, 5, 15.\)
- The divisors of \(36\) are \(1, 2, 3, 4, 6, 9, 12, 18,36.\)
Now you can see that there are two divisors that are common to both \(15\) and \(36\) are \(1\) and \(3\).
You pick the one that is bigger, so \(3\) is the greatest common divisor of \(15\) and \(36\).
Now in order to find the GCD for bigger numbers, finding the common divisors method will become a very long and tedious process. That is why you use the Greatest Common Divisor Algorithm, also known as the Euclidean Algorithm.
Greatest Common Divisor Algorithm
The Euclidean algorithm is a computational process that computes the GCD of two positive integers. It uses remainders to find the greatest common divisor between the two numbers.
First let's look at the process of long division. Take two positive integers, \(a\) and \(b\) such that \(a>b\). Euclidean division is a process to write \(a\) and \(b\) in the form
\[a=qb+r\]
where \(q\) is a positive integer called the quotient, and \(0\leq r<b\) is called the remainder.
Let's look at a quick example of long division.
Taking the integers \(44\) and \(17\) and performing long division gives
$$\begin{array}{r}2\phantom{)} \\ 17{\overline{\smash{\big)}\,44\phantom{)}}}\\ \underline{-~\phantom{(}0\phantom{-b)}}\\ 44\phantom{)}\\ \underline{-~\phantom{()}34}\\ 10\phantom{)} \end{array}$$
Therefore, 44 divided by 17 gives the quotient 2 with remainder 10.
So let \(a=44\) and \(b=17\), then substituting into the formula gives
\[\begin{align} a&=qb+r \\ 44&=2\cdot17+10. \end{align}\]
Steps of the Euclidean Algorithm
Take two positive integers, \(a\) and \(b\) such that \(a>b\). To compute the \(\text{GCD} (a,b)\), the steps of the Euclidean Algorithm are:
Step 1: Divide \(a\) by \(b\) so that \(a=bq_1+r_1\) where \(r_1\) is the remainder when \(b\) is divided by \(a\). Then
\[\text{GCD} (a,b)=\text{GCD} (b,r_1) .\]
Step 2: Since \(b>r_1\), divide \(b\) by \(r_1\) so that \(b=r_1q_2+r_2\). Then
\[\text{GCD} (b,r_1)=\text{GCD} (r_1,r_2).\]
Step 3: Since \(r_1>r_2\), you know that \(r_1=r_2q_3+r_3\). That means
\[\text{GCD} (r_1, r_2)=\text{GCD} (r_2, r_3).\]
Step 4: Repeat this for the remainders until \(r_k=0\).
Step 5: Then you have
\[\begin{align} \text{GCD} (a,b)&=\text{GCD} (b,r_1) \\ &=\text{GCD} (r_1, r_2) \\ &=\vdots \\ &=\text{GCD} (r_{k-1}, r_k) \\ &=\text{GCD} (r_{k-1},0) \\ &=r_{k-1} . \end{align}\]
Therefore, the GCD is the last non-zero remainder of the Euclidean division. Of course, the best way to understand this is with some examples.
Greatest Common Divisor Examples
Let's start with one where you know that the answer is supposed to be \(1\), so you can see that the Euclidean Algorithm works.
Use the Euclidean Algorithm to find the GCD of \(44\) and \(17\).
Answer:
Step 1: Since \(44>17\), divide \(44\) by \(17\) so that \(44=17\cdot 2+10\) where \(10\) is the remainder when \(44\) is divided by \(17\). Then
\[\text{GCD} (44,17)=\text{GCD} (17,10) .\]
Step 2: Now divide \(17\) by \(10\) so that \(17=1 \cdot 10+7\). So
\[\text{GCD} (17,10)=\text{GCD} (10,7).\]
Step 3: Now \(10=1\cdot 7+3\), so
\[\text{GCD} (10,7)=\text{GCD} (7,3) .\]
Step 4: Here \(7=2\cdot 3+1\), so
\[\text{GCD} (7, 3)=\text{GCD} (3, 1).\]
Step 5: In this step, \( 3=1\cdot 3\) with no remainder. Therefore, \(\text{GCD} (44,17)=1\).
Let's take a look at another example.
Find the GCD of \(12\) and \(30\) using the Euclidean Algorithm.
Answer:
Since \(30 > 12\), \(a=30\) and \(b=12\) in the Euclidean Algorithm.
Step 1: You now have to write \(a\) in the form \(a=bq+r\), which gives you \(30=(12\cdot 2)+6\).
You know that \(\text{GCD} (a, b) =\text{GCD} (b, r)\), so
\[\text{GCD} (30, 12) = \text{GCD} (12, 6).\]
Step 2: Now, let \(b=12\) and \(r_1=6\) and carry out the same process again. That means \(12=(6\cdot 2)+0\).
Now \(r_1=6\) and \(r_2=0\), so
\[\text{GCD} (r_1,r_2)=\text{GCD} (6,0)=6 .\]
Step 4: Wait, the algorithm ends as soon as you get a remainder of \(0\), which you already have! That means you get to skip Step 4.
Step 5: Now you know that
\[ \begin{align} \text{GCD} (6,0) &=\text{GCD} (12,6) \\ &=\text{GCD} (30,12) \\ &=6 . \end{align}\]
Therefore the GCD of \(30\) and \(12\) is \(6\).
Greatest Common Divisor of Three Numbers
You have already looked at examples where you found the GCD of three numbers! Remember it made use of
the Associative Property:
\[\text{GCD} (a, \text{GCD} (b, c)) = \text{GCD} (\text{GCD} (a, b),c) .\]
If you like you can use the Euclidean Algorithm to find the GCD of two of the numbers and then use it again to find the GCD of all three.
Find the greatest common divisor of \(32\), \(254\) and \(372\).
Answer:
First you would use the Euclidean Algorithm to find \(\text{GCD} (32,254) = 2\). Then you can use the Euclidean Algorithm again to see that \(\text{GCD} (2,372) =2\).
So by the Associative Property,
\[ \begin{align} \text{GCD} (32, 254, 372) &=\text{GCD} (\text{GCD} (32,254), 372) \\ & =\text{GCD} (2,372)\\ &=2 . \end{align}\]
What about the GCD of polynomials, you may ask?
Greatest Common Divisor of Polynomials
Finding the GCD of two polynomials is very similar to finding the GCD of two numbers. It requires Factoring Polynomials, and sometimes long division of polynomials. For more information on those topics see Operations with Polynomials and Factoring Polynomials.
Greatest Common Divisor - Key takeaways
- The greatest common divisor of a set of numbers is the largest natural number by which all the numbers in the set can be divided by.
- The GCD can be found by finding all the factors of the set of numbers and identifying the largest factor that is common to all the numbers in that set. Alternatively, the GCD can be determined using the Euclidean Algorithm. This means for two integers \(a\) and \(b\), writing \(a\) in the form \(a=bq+r\) and repeating this process until \(r=0\). Both methods give you the same answer.
- The GCD satisfies the following properties:
Identity Property: \(\text{GCD} (a,0)=|a|\).
The Commutative Property: \(\text{GCD} (a,b)=\text{GCD} (b,a)\).
The Associative Property: \(\text{GCD} (a, \text{GCD} (b, c)) = \text{GCD} (\text{GCD} (a, b),c)\).
The Distributive Property: \(\text{GCD} (ab, ac) =a \text{GCD} (b,c)\).
Learn with 0 Greatest Common Divisor flashcards in the free StudySmarter app
Already have an account? Log in
Frequently Asked Questions about Greatest Common Divisor
How do you find the greatest common divisor?
Either by finding all the common factors of all the numbers in the set of numbers and identifying the highest one or by using Euclid´s algorithm
What is the greatest common divisor?
It is the highest positive integer by which a given set of numbers can all be divided by
What is an example of greatest common divisor?
Let´s take the numbers 10 and 15. We can list all the factors of 10 and 15:
10: 1, 2, 5, 10
15: 1, 3, 5, 15
And now we can see that the greatest common divisor of 10 and 15 is 3
What is the greatest common divisor of 24 and 32?
If we take the factors of both numbers we get:
24=2·2·2·3
32=2·2·2·2·2
Therefore, the largest natural number that divides 24 and 32 is 2·2·2=8.
About StudySmarter
StudySmarter is a globally recognized educational technology company, offering a holistic learning platform designed for students of all ages and educational levels. Our platform provides learning support for a wide range of subjects, including STEM, Social Sciences, and Languages and also helps students to successfully master various tests and exams worldwide, such as GCSE, A Level, SAT, ACT, Abitur, and more. We offer an extensive library of learning materials, including interactive flashcards, comprehensive textbook solutions, and detailed explanations. The cutting-edge technology and tools we provide help students create their own learning materials. StudySmarter’s content is not only expert-verified but also regularly updated to ensure accuracy and relevance.
Learn more