Warning: Missing argument 2 for ted_filter_oembed_amp_iframe() in /home/customer/www/torontotutorteam.ca/public_html/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 = q₁b + r₁ 
if r₁ = 0, then gcd (a, b) = b
if r₁ ≠ 0, b = q₂r₁ + r₂
if r₂ = 0, then gcd (a, b) = r₁
if r₂ ≠ 0, r₁ = q₃r₂ + r₃
.
.
.
if r_n = 0, r_n-2 = q_nr_n-1 + r_n, then gcd (a, b) = r_n-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.