How to Find the Greatest Common Divisor of Two Integers

Author Info

Last Updated: July 29, 2019 Fact Checked

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]
X
Research source}

Method 1

Method 1 of 2:

Using the Divisor Algorithm

Download Article

2
Know your vocabulary: when you divide 32 by 5,^{[2]
X
Research source}
- - 32 is the dividend
  - 5 is the divisor
  - 6 is the quotient
  - 2 is the remainder (or modulo).
Advertisement
That will be the dividend, and the smaller the divisor.^{[3]
X
Research source}
(dividend) = (divisor) * (quotient) + (remainder)^{[4]
X
Research source}
^{[5]
X
Research source}
^{[6]
X
Research source}
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.
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.

Method 2

Method 2 of 2:

Using Prime Factors

Download Article

^{[7]
X
Research source}
2
Find the prime factorization of the numbers, and list them out as shown.^{[8]
X
Research source}
- 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
3
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
4
Multiply the common factors together.^{[9]
X
Research source}
- In the case of 24 and 18, multiply 2 and 3 together to get 6. Six is the greatest common factor of 24 and 18.
- In the case of 50 and 35, there is nothing to multiply. 5 is the only common factor, and therefore the greatest.

Community Q&A

Search

Add New Question

Question

How do I find the gcd of three integers?

Donagan

Top Answerer

Find all of the divisors of each of the integers, and note the largest one that's common to all three.

Thanks! We're glad this was helpful.
Thank you for your feedback.
If wikiHow has helped you, please consider a small contribution to support us in helping more readers like you. We’re committed to providing the world with free how-to resources, and even $1 helps us in our mission. Support wikiHow
Yes No

Not Helpful 6 Helpful 16
Question

How do I round off 93,678,563 to the nearest 10,000?

Donagan

Top Answerer

Look at the digit in the 1,000's place: it's 8, so you round up to 93,680,000.

Thanks! We're glad this was helpful.
Thank you for your feedback.
If wikiHow has helped you, please consider a small contribution to support us in helping more readers like you. We’re committed to providing the world with free how-to resources, and even $1 helps us in our mission. Support wikiHow
Yes No

Not Helpful 2 Helpful 8
Question

What is a multiplicative inverse?

Donagan

Top Answerer

A multiplicative inverse is the reciprocal of a number.

Thanks! We're glad this was helpful.
Thank you for your feedback.
If wikiHow has helped you, please consider a small contribution to support us in helping more readers like you. We’re committed to providing the world with free how-to resources, and even $1 helps us in our mission. Support wikiHow
Yes No

Not Helpful 6 Helpful 6

See more answers

Ask a Question

200 characters left

Include your email address to get a message when this question is answered.

Submit

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
Helpful 0 Not Helpful 0
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
Helpful 0 Not Helpful 1
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
Helpful 0 Not Helpful 0