Download ArticleDownload ArticleHow.com.vn is a “wiki,” similar to Wikipedia, which means that many of our articles are co-written by multiple authors. To create this article, 40 people, some anonymous, worked to edit and improve it over time.
This article has been fact-checked, ensuring the accuracy of any cited facts and confirming the authority of its sources.
This article has been viewed 611,390 times.
Learn more...
The Greatest Common Divisor (GCD) of two whole numbers, also called the Greatest Common Factor (GCF) and the Highest Common Factor (HCF), is the largest whole number that's a divisor (factor) of both of them. For instance, the largest number that divides into both 20 and 16 is 4. (Both 16 and 20 have larger factors, but no larger common factors -- for instance, 8 is a factor of 16, but it's not a factor of 20.) In grade school, most people are taught a "guess-and-check" method of finding the GCD. Instead, there is a simple and systematic way of doing this that always leads to the correct answer. The method is called "Euclid's algorithm." If you want to know how to truly find the Greatest Common Divisor of two integers, see Step 1 to get started.[1]
Steps
Drop any negative signs.
Know your vocabulary: when you divide 32 by 5,[2]- 32 is the dividend
- 5 is the divisor
- 6 is the quotient
- 2 is the remainder (or modulo).
Advertisement
Identify the larger of the two numbers. That will be the dividend, and the smaller the divisor.[3]
Write out this algorithm: (dividend) = (divisor) * (quotient) + (remainder)[4]
Put the larger number in the spot for dividend, and the smaller number as the divisor.[5]
Decide how many times the smaller number will divide into the larger number, and drop it into the algorithm as the quotient.
Calculate the remainder, and substitute it into the appropriate place in the algorithm.[6]
Write out the algorithm again, but this time A) use the old divisor as the new dividend and B) use the remainder as the new divisor.
Repeat the previous step until the remainder is zero.
The last divisor is the greatest common divisor.
Here is an example, where we are trying to find the GCD of 108 and 30:
Notice how the 30 and the 18 in the first line shift positions to create the second line. Then, the 18 and 12 shift to create the third line, and the 12 and 6 shift to create the fourth line. The 3, 1, 1, and 2 that follow the multiplication symbol do not reappear. They represent how many times the divisor goes into the dividend, so they are unique to each line.
Drop any negative signs.[7]
Find the prime factorization of the numbers, and list them out as shown.[8]- Using 24 and 18 as the example numbers:
- 24- 2 x 2 x 2 x 3
- 18- 2 x 3 x 3
- Using 50 and 35 as the example numbers:
- 50- 2 x 5 x 5
- 35- 5 x 7
- Using 24 and 18 as the example numbers:
Identify all common prime factors.- Using 24 and 18 as the example numbers:
- 24- 2 x 2 x 2 x 3
- 18- 2 x 3 x 3
- Using 50 and 35 as the example numbers:
- 50- 2 x 5 x 5
- 35- 5 x 7
- Using 24 and 18 as the example numbers:
Finished.
Community Q&A
- QuestionHow do I find the gcd of three integers?
DonaganTop AnswererFind all of the divisors of each of the integers, and note the largest one that's common to all three. - QuestionHow do I round off 93,678,563 to the nearest 10,000?DonaganTop AnswererLook at the digit in the 1,000's place: it's 8, so you round up to 93,680,000.
- QuestionWhat is a multiplicative inverse?DonaganTop AnswererA multiplicative inverse is the reciprocal of a number.
Tips
- One way to write this, using the notation <dividend> mod <divisor> = the remainder is that GCD(a,b) = b if a mod b = 0, and GCD(a,b) = GCD(b, a mod b) otherwise.Thanks
- As an example, let's find GCD(-77,91). First, use 77 instead of -77, so GCD(-77,91) becomes GCD(77,91). Now, 77 is less than 91, so we should swap them, but let's see how the algorithm takes care of that if we don't. When we calculate 77 mod 91, we get 77 (since 77 = 91 x 0 + 77). Since that's not zero, we switch (a, b) for (b, a mod b) and that gives us: GCD(77,91) = GCD(91,77). 91 mod 77 gives 14 (remember, that means 14 is the remainder). Since that's not zero, swap GCD(91,77) for GCD(77,14). 77 mod 14 gives 7 which is not zero, so swap GCD(77,14) for GCD(14,7). 14 mod 7 is zero, since 14 = 7 * 2 with no remainder, so we stop. And that means: GCD(-77,91) = 7.Thanks
- This technique is very useful when reducing fractions. By the above example, the fraction -77/91 reduces to -11/13 because 7 is the greatest common divisor of -77 and 91.Thanks
References
- ↑ https://brilliant.org/wiki/greatest-common-divisor/
- ↑ https://www.math-only-math.com/dividend-divisor-quotient-and-remainder.html
- ↑ http://sites.math.rutgers.edu/~greenfie/gs2004/euclid.html
- ↑ http://sites.math.rutgers.edu/~greenfie/gs2004/euclid.html
- ↑ https://www.youtube.com/watch?v=h86RzlyHfUE
- ↑ https://www.youtube.com/watch?v=h86RzlyHfUE
- ↑ https://www.sparknotes.com/math/prealgebra/wholenumbers/section4/
- ↑ https://www.sparknotes.com/math/prealgebra/wholenumbers/section4/
- ↑ https://www.youtube.com/watch?v=25QB-JjZLxY
About This Article
Did this article help you?
⚠️ Disclaimer:
Content from Wiki How English language website. Text is available under the Creative Commons Attribution-Share Alike License; additional terms may apply.
Wiki How does not encourage the violation of any laws, and cannot be responsible for any violations of such laws, should you link to this domain, or use, reproduce, or republish the information contained herein.
- - A few of these subjects are frequently censored by educational, governmental, corporate, parental and other filtering schemes.
- - Some articles may contain names, images, artworks or descriptions of events that some cultures restrict access to
- - Please note: Wiki How does not give you opinion about the law, or advice about medical. If you need specific advice (for example, medical, legal, financial or risk management), please seek a professional who is licensed or knowledgeable in that area.
- - Readers should not judge the importance of topics based on their coverage on Wiki How, nor think a topic is important just because it is the subject of a Wiki article.
