Learning Materials
Features
Discover
Suppose you have two lengths of rope. One piece is \(36\) inches long and the other is \(24\) inches. You want to cut both pieces into strips of equal length that are as long as possible. How should you cut the pieces?
Millions of flashcards designed to help you ace your studies
Sign up for freeWhat is StudySmarter?
How does StudySmarter help me study more efficiently?
Where can I find more explanations like this?
What's smart about StudySmarter's flashcards?
Can I create my own content on StudySmarter?
How does spaced repetition work in StudySmarter flashcards?
What can you do with flashcards in StudySmarter?
Is StudySmarter a science-based learning platform?
How do StudySmarter's smart learning plans support your exam prep?
Can you create your own study sets in StudySmarter?
What is StudySmarter?
How does StudySmarter help me study more efficiently?
Where can I find more explanations like this?
What's smart about StudySmarter's flashcards?
Can I create my own content on StudySmarter?
How does spaced repetition work in StudySmarter flashcards?
What can you do with flashcards in StudySmarter?
Is StudySmarter a science-based learning platform?
How do StudySmarter's smart learning plans support your exam prep?
Can you create your own study sets in StudySmarter?
Achieve better grades quicker with Premium
Geld-zurück-Garantie, wenn du durch die Prüfung fällst
Did you know that StudySmarter supports you beyond learning?
Review generated flashcards
Start learning or create your own AI flashcards
Team Greatest Common Divisor Teachers
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.
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?
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.
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:
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\):
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.
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}\]
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.
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\).
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?
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.
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)\).
Sign up for free to gain access to all our flashcards.
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.
At StudySmarter, we have created a learning platform that serves millions of students. Meet the people who work hard to deliver fact based content as well as making sure it is verified.
Lily Hulatt is a Digital Content Specialist with over three years of experience in content strategy and curriculum design. She gained her PhD in English Literature from Durham University in 2022, taught in Durham University’s English Studies Department, and has contributed to a number of publications. Lily specialises in English Literature, English Language, History, and Philosophy.
Get to know Lily
Gabriel Freitas is an AI Engineer with a solid experience in software development, machine learning algorithms, and generative AI, including large language models’ (LLMs) applications. Graduated in Electrical Engineering at the University of São Paulo, he is currently pursuing an MSc in Computer Engineering at the University of Campinas, specializing in machine learning topics. Gabriel has a strong background in software engineering and has worked on projects involving computer vision, embedded AI, and LLM applications.
Get to know Gabriel
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 moreSave explanations to your personalised space and access them anytime, anywhere!
Sign up with Email Sign up with AppleBy signing up, you agree to the Terms and Conditions and the Privacy Policy of StudySmarter.
Already have an account? Log in
Sign up to highlight and take notes. It’s 100% free.
Explanations 
Flashcards 
StudySmarter AI 
Notes 
Study Plans 
Study Sets 
Exams 
Find a job 
Student Deals 
Magazine 
Mobile App 
