Euclid's division algorithm

On this page we will discuss Euclid's Division Algorithm that would have been used in Ancient Greece. The Division Algorithm is very similar to that of modern-day long division. It is a theorem that states for any two positive integers, a and b, there exist unique integers, q and r, such that b=aq+r with 0≤r<b

First, we will quickly prove this theorem to be true.

Proof:

First, we show that q and r exist. Consider the set S = {b − aq |x ∈ Z, b − aq ≥ 0} (or the set of all integers of the form b − aq with an integer q which happen to be non-negative).

Now we must show that S is nonempty. That is simple: if b ≥ 0, then b ∈ S (just take q = 0), while if b < 0, then take q = b and find that b(1 − a) ∈ S.

So S is nonempty and thus some q and r exist.

Now we show that q and r are unique.

Assume for the sake of contradiction that we have two sets integers q and r, and q' and r' such that b = aq + r = aq' + r' and both 0 ≤ r, r'< a.

Thus r − r' = (q' − q)a.

Note that, since 0 ≤ r < k and 0 ≤ r' < k, we have that |r − r'| < a.

We thus have that a > |r − r'| = |q' − q|a ≥ a,

and this would lead us to an absurd conclusion a > a which proves the uniqueness of q and r.

Take a look at this example of using Euclid's division Algorithm to find the highest common factor of two numbers. NCERT solutions for class 10 maths on Real numbers part 2, Euclid’s. (n.d.). Retrieved October 12, 2022, from https://suresolv.com/high-school-math/ncert-solutions-class-10-maths-real-numbers-part-2-euclids-division-algorithm-an

In this example, we would find the following equations according to Euclid's Division Algorithm:

867 = 255 * 3 + 102

255 = 102 * 2 + 51

102 = 51 * 2 + 0

Euclidean Algorithm

Applying the Euclid's division algorithm iteratively, like in the example above, leads to an interesting result: the greatest common divisor (GCD) of a and b.

This result is called the Euclidean Algorithm.

Iterating the division algorithm gives us the following result (Note: we cease iterating the function when ${\bf{r}}_n$ =0):

b = a $q_1$ + $r_1$ , 0 < $r_1$ < a

a = $r_1$ $q_2$ + $r_2$, 0 < $r_2$ < $r_1$

$r_1$ = $r_2$ $q_3$ + $r_3$ , 0 < $r_3$ < $r_2$

.

.

.

$r_{n-3}$ = $r_{n-2}$ $q_{n-1}$ + $r_{n-1}$ , 0 < $r_{n-1}$ < $r_{n-2}$

$r_{n-2}$ = $q_n$ $r_{n-1}$ + 0

Now, this tells us the $r_{n-1}$ is the greatest common divisor of b. In shorthand, this can be expressed such that d = ax +by where d is the greatest common divisor of a and b. For the sake of brevity, I won't prove this, but hopefully you can see why this is true.

While this seems very complicated when looking at the abstract version, working through a concrete version is much simpler!

Mathematics in Cryptography: Part 1 - Developer Community SASTRA. (2022, January 6). Medium. Retrieved October 12, 2022, from https://medium.com/dsc-sastra-deemed-to-be-university/mathematics-in-cryptography-part-1-3749e5b354c

The Euclidean Algorithm is still used today to find the greatest common divisor of two or more numbers.

Sources:

Euclid’s Division Algorithm - Real Numbers | Class 10 Maths. (2020, November 24). GeeksforGeeks. https://www.geeksforgeeks.org/euclids-division-algorithm-real-numbers-class-10-maths/

Mays, M. E. (1985, June). ITERATING THE DIVISION ALGORITHM [Review of ITERATING THE DIVISION ALGORITHM]. https://www.researchgate.net/profile/M-Mays/publication/267836205_ITERATING_THE_DIVISION_ALGORITHM/links/549171e80cf222ada8591139/ITERATING-THE-DIVISION-ALGORITHM.pdf

Rediske de Almeida, M. V., Ribeiro, M., & Fiorentini, D. (2021). Mathematical Specialized Knowledge of a Mathematics Teacher Educator for Teaching Divisibility. PNA, 15(3), 187–210. https://doi-org.ezproxy.shsu.edu/10.30827/pna.v15i3.15778