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.
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:
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:
$ 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:
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.
$ 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$
