Greatest Common Divisor


Warning: Missing argument 2 for ted_filter_oembed_amp_iframe() in /home/kawalski/public_html/torontotutorteam.ca/wp-content/plugins/jetpack/modules/shortcodes/ted.php on line 108

Learn how to find the greatest common divisor between two or more numbers using the Euclidean Algorithm.

The greatest common divisor is expressed as:

gcd (a, b)

Where a and b are the two numbers you want to find the greatest common divisor for.

The first step is the division algorithm, which states:

a = qb + r

Where a, b, q, and r are integers, and |a| > |b| > 0
q is the quotient and r is the remainder

For example, let

a = 51 and b = 10
q = 5 and r = 1, so 51 = 5*(10) + 1

Now the algorithm is as follows:

a = q1b + r
if r1 = 0, then gcd (a, b) = b
if r1 ≠ 0, b = q2r1 + r2
if r2 = 0, then gcd (a, b) = r1
if r2 ≠ 0, r1 = q3r2 + r3
.
.
.
if rn = 0, rn-2 = qnrn-1 + rn, then gcd (a, b) = rn-1

The key is that at each step if the remainder is not zero, the divisor becomes the new dividend, and the remainder becomes the new divisor.

Let’s look at an example:

gcd (1234, 5678)
5678 = 4*(1234) + 742
1234 = 1*(742) + 492
742 = 1*(492) + 250
492 = 1*(250) + 242
250 = 1*(242) + 8
242 = 30*(8) + 2
8 = 4*(2) = 0

We finally got a remainder of 0! This means rn = 0, which means rn-1, which is 2, is the greatest common divisor.

Now consider 3 numbers:

gcd (2, 6, 17)
= gcd (gcd (2, 6), 17)   The way to do this is to simply break the problem into gcd’s between a pair of numbers
= gcd (2, gcd (6, 17))   We can either initially consider the first pair (2, 6), or the second pair (6, 17)
= gcd (2, 1)
= 1

Here are some more examples you can try on your own:

gcd (12345, 1745)
Answer = 5

gcd (21, 39, 1044)
Answer = 3

If you prefer video:

You can also check out more great math tutorials.

Leave a comment



toronto tutor team

Contact Info

Ready to start learning? Give us a call or send us an email to book a tutoring session today.

+1 855-775-4473
info@torontotutorteam.ca

Use the message icon below to live chat with a member of the Team right now!

Copyright 2016 © All Rights Reserved