Latest Tweets

Free math worksheets

Euclidean algorithm

euclid of alexandria

Euclid of Alexandria was a Greek mathematician. He was called the “Father of Geometry”. He wrote one of the most influential works in the history of mathematics – Elements.

Although Elements are mostly about geometry, Elements also include number theory. In this lesson we’ll give a little insight of this great mathematicians mind and his influence in the number theory.

euclid of alexandria

Image credit: Wikimedia Commons

The Euclidean Algorithm is a method for finding the greatest common divisor of two integers. Before showing the exact algorithm first we should set few rules and notations.

If a|b and a|c, we say that a is the common divisor of numbers b and c.

If at least one of numbers b and c is different from zero, then there exist only finitely many common divisors of b and c. The greatest of them is called the greatest common divisor of b and c. GCD is denoted as (b, c).

If we have two numbers whose greatest common divisor is one, we say that those two numbers are relatively prime. For example 40 and 13 are relatively prime. We denote this as:

(40, 13) = 1 \rightarrow 40 and 13 are relatively prime numbers
 

You also don’t necessarily have to observe only two numbers. More than two numbers can also be relatively prime. If we have numbers b_1, b_2, b_3, ... ,bn whose only common divisor is 1, we say that those numbers are relatively prime. Also if every pair of those numbers is relatively prime we say that there are pairwise relatively prime.

Lemma 1. If b = aq + r, 0 \le r < a, a > 0, then (a, b) = (a, r).

Put in words, this lemma tells us that if we have a number b, that is divisible with number a with remainder r, then the greatest common divisor from a and b will be the same as the greatest common divisor of a and r.

As an example we can take 6 and 4. We know that 6 = 4 * 1 + 2. We can see now that (6, 4) = (6, 2) = 2

Proof. Let’s say that (a, b) = d_1, (a, r) = d_2.

b = aq + r \rightarrow r = b - aq \rightarrow d_1 | r .This means that d1 is the common divisor of a and r.

Since we got that d_1 | a and that d_2 | b we can conclude that d_1 \le d_2.

b = aq + r \rightarrow d_2 | b. This means that d_2 is the common divisor of a and b.

From here we got that d_2 | a and that d_2 | b which means that d_2 \le d_1.

We now got that d_1 \le d_2 and that d_2 \le d_1 which can only mean that d_1 = d_2.

 

Algorithm

Let’s assume that with repeated application of the remainder theorem we got the following string of equalities:

b = aq_1 + r_1, 0 \le r_1 < a
a = r_1q_2 + r_2, 0 \le r_2 \le r1

r1 = r_2q_3 + r_1, 0 < r_3 < r_2

r(n - 2) = r(n - 1)qn + rn, 0 < rn < r(n - 1)

r(n - 1) = rnqn + 0

The procedure ends when we get remainder equal to zero. The procedure has to end in finally many steps.

Lemma 1 implies that the greatest common divisor of a and b is equal to rn because:

(a, b) = (a, r_1) = (r_1, r_2) = ... = (r(n - 1), rn) = rn

This means that (a, b) is equal to the last non trivial remainder in the upper procedure.

This process for finding GCD is called the Euclidean algorithm.

Let’s see how this algorithm works in practice.

Example Find GCD of 53357 and 547.

First we’ll divide 53358 with 548 and write it down as a sum of a product and remainder.

53348 = 97 * 548 + 192
548 = 2 * 192 + 164

192 = 1 * 164 + 28

164 = 5 * 28 + 24

28 = 1 * 24 + 4

24 = 6 * 4 + 0

Since 4 is the last non trivial remainder this means that (53358, 548) = 4

Leave a comment

Enter Verification code: * Time limit is exhausted. Please reload CAPTCHA.

Shares