4.8 • +11k Ratings
Find Study Materials for
- betray雷竞技
-
Exams Exam preparation made easy. -
Textbooks Free and expert-verified textbook solutions. - app雷竞技
雷电竞官方地址
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?
You can use the concept ofthe greatest common divisorto 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 divisorof a group of integers, often abbreviated toGCD,被定义为最大可能的自然麻木er 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 fromsimplifying fractionsand 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,
\[开始\ {GCD}{对齐}\文本(4,0)& = \ {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 afactorof 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):
找到所有通讯on 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 algorithmis 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 thequotient,and \(0\leq r
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\ \(文本{GCD} (2, 372) =2\).
通过关联属性,
\[ \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 seeOperations with PolynomialsandFactoring 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)\).
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
It is the highest positive integer by which a given set of numbers can all be divided by
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
Be perfectly prepared on time with an individual plan.
Test your knowledge with gamified quizzes.
Create and find flashcards in record time.
Create beautiful notes faster than ever before.
Have all your study materials in one place.
Upload unlimited documents and save them online.
Identify your study strength and weaknesses.
Set individual study goals and earn points reaching them.
Stop procrastinating with our study reminders.
Earn points, unlock badges and level up while studying.
Create flashcards in notes completely automatically.
创造最美丽的学习伙伴rials using our templates.
Sign up to highlight and take notes. It’s 100% free.
