Euclidian Algorithm(Math)

Hi all !
I,m here again with some interesting article. It's not about programming or databases this time.
It's algorithm. Actually It's Math. We all know it as Euclidian Algorithm(Euclid in Math).

Let's start this then !!!


The "Euclidian algorithm" is an algorithm that finds the greatest common divisor of 2 numbers.Discovered by Euclid in the mid 4th century BC, it's referred to as the world's oldest algorithm.



As an example, let's consider the largest common divisor of 1112 and 695.

With the usual method, we factorize the 2 numbers into prime numbers.

and the greatest common divisor(GCD) from the prime numbers they share.

Now we know that the greatest common divisor for 1112 and 695 is 139.

However, with this method, the larger the 2 numbers get, the more difficult prime factorization becomes.With Euclidian Algorithm, we can find greatest common divisors more efficiently.

Before we Enter an explanation of the Euclidian Algorithm,let's explain the mod operation.The mod operation is an operation that finds the remainder of a division.For A mod B, we get C, the remainder of A divided by B.

Let's show some example operations using concrete numbers.

Now ,let's take a look at the Euclidian algorithm in action.

First we find the remainder of the larger number divided by the smaller number.

in other words we will carry out a mod operation with the larger and smaller numbers.

The result of the division found 417 to be remainder.

This time , we carry out a mod operation with the previous divisor,695 ,and the previous remainder, 417.

We got 278

We repeat the same operation , carrying out a mod operation with 417 and 278.

We got 139

We carry out a mod operation with 278 and 139.

We got 0.

In other words,278 is divisible by 139.

When the remainder is 0, the divisor of the last operation, 139, is found to be the greatest common divisor of 1112 and 695.

How is the Euclidian algorithm able to find the greatest common divisor?

Let's consider that question using the diagram.

I will try expressing 1112 and 695 in terms of bar length.

I will add segments in increments of n, the greatest common divisor.

It's been determined that 139 is the greatest common divisor, so far convenience, 1112 was given 8 segments and 695 was given 5 segments.In actually, it is not known how many segments are on each bar.However, we do know that both 1112 and 695 are multiples of a greatest common divisor, n.

Here ,like in the earlier operation, we will find the remainder of the larger number divided by the smaller number.

We got 417. From the diagram, we can see that 417 is a number also neatly divided into segments of width n.

I will repeat the mod operation like we did earlier.

When 695 is divided by 417, we get a remainder of 278.This remainder of 278 is also an integral multiple of n, in other words, it has the same greatest common divisor 

We repeat the division again.

Because 278 is divisible by 139, the remainder is 0.

It is here that we learn that the greatest common divisor, n is 139.

In this way, the Euclidian algorithm is able to find the greatest common divisor by simply repeating divisions.

A big advantage is that even if the 2 target numbers are huge, the algorithm is able to find the greatest common divisor with a standard procedure.

That's it guys!!!

-ThilanJR10-