Is there an easy way to find the greatest common divisor? - The Euclidean algorithm explained

How can you find the greatest common divisor of two integers by using an algorithm? 

The Euclidean Algorithm is a method for finding the greatest common divisor (gcd) of two positive integers, a and b. The greatest common divisor is the largest number to divide a and b, without leaving a remainder. The algorithm was given in book VII of Euclid’s Elements. Euclid (fl. 300 BC) was a Greek mathematician and he is often referred as the “father” of geometry. 

A scheme of the Euclidean algorithm that continues until the greatest common divisor is found

The modern Euclidean algorithm:  

Steps: 

Searching for the gcd of two integers, two numbers are necessary at first: a and b. Divide the greater number (a>b or b>a) by the smaller number a or b. In this case, a is the bigger number. If a=0, the task is complete and the gcd is b and vice versa. If the gcd of a natural number and 1 is searched, the gcd is 1 and when the gcd =1, the numbers are called “coprime” as they have no common divisor bigger then 1.  

For the first step,  

   

are the resulting numbers from the division of a/b. It multiplies b as many times as it "fits" into a. The remainder of a/b (if there is one), is .

Now divide the smaller number, in this case b, by the remainder from the first division. It is  

The remainder of the division  above, is

The remainder of the first division is now divided by the remainder of the second step.  

If there is a remainder after the division of step 3, it is divided by the remainder of step 2. This process continues until the remainder

The divisor from the step before the remainder 

,is the gcd of a and b.

It is:  

,so the last nonzero remainder equals the gcd. The Euclidean Algorithm is a recursive algorithm, because the same step is repeated and the numbers used in the steps are a result of the step before, until it produces the gcd.

It is:

The scheme for the algorithm is the following:  

                           .

                           .

Each output from every step is an input for the following step until the goal to find a quotient and a remainder to satisfy the equations above, is reached. 

Example: 

Input:

a =231 

b = 63  

Dividing 231 by 63, a remainder of 42 occurs. 63 divided by 42 is 1, plus a remainder of 21. As in the last line, where the remainder of 42/21 equals 0, the remainder of the line before (21) is the gcd of a and b.

Output 

d =21 = gcd(a,b)  

Theorem visualisation:

If d divides a and b, it also divides a-b -> {a,b},{a-b,b} have the same set of common divisors. For the case of a>b, imagine the number a as a package, the divisor creates. Let’s say a/d= 5 packages and b/d= 2 packages. Subtracting a from b (a-b), 3 packages are left and as each package is created by the divisor, a-b has the same common divisor as a or b -> subtracting packages leaves packages and each package has the same divisor. The remainder r is simply a package like the packages taken away from a.  

The illustration above shows two bars of which the blue one is bigger than the red one. To simplify it, red (r) is the biggest common divisor of the two numbers already as it fits 4 times into the blue bar. If the red bar is subtracted from the blue bar, 3 pieces are left which are all as big as the red piece. Therefore, the resulting green bar is 3*r long. This is the same as mentioned above: If d divides a (blue bar) and b (red bar), it also divides a-b (green bar) -> If one piece would be "6" long and the blue bar is 4*6=24 "long", 24-6=18 has got the same common divisor (6) as 6 and 24. Having a remainder r (yellow bar), it still works. In this case b= 2,5*r, leaving a remainder of 0,5*r. Because r doesn't fit into b without leaving a remainder, the yellow bar is left. The yellow bar shows, it is r/2 and r+the light blue bar creates the blue bar: Light blue bar (lb)= 1,5*r and adding one r, the equation for b is: lb+r=b. Both the remainder r, the blue bar and the red bar have got the same gcd.

Conclusion from the bar illustration:

d = gcd(a,b) 

Since a and b are both multiples of d:

a=d*k   

b=j*k 

(d & j are coprime to avoid creating a common divisor D, for which d<D) 

Because d divides a and b:

a-b*k is a package too. ->green bar

Therefore: r =a-bq = dk-q*jk = (j-qk)*d

This principle works until

    

After this condition is fulfilled, the gcd is found:

Changing the equation for the algorithm, it is clear that r and b have the same gcd as (a,b). 

Example with a rectangle

(54,24) 

A rectangle with the area a*b can visualize it too. Searching the gcd of 54 and 24, the side lengths equal the input numbers. As in the first step, 24 fits two times into 54, so two rectangles are created inside the area with area of a=24*24. This division leaves a remainder of 6. 24 is 4 times 6 and this is displayed by the 4 remaining yellow rectangles, of which the whole a*b area can be made up from -> 6 is the biggest common divisor d of 54 & 24. 

54 = 2*24 +6 

24 = 4 *6 +0  

Conclusion

Such an algorithm is a fast way to find the gcd of two numbers. There are extended versions of this algorithm and many programming implementations to follow the logic of it's method from different approaches.

Thanks for reading

Have a nice day :)

Source

Text

https://en.wikipedia.org/wiki/Euclid

https://de.serlo.org/mathe/zahlen-groessen/teiler-primzahlen/teiler-vielfache/euklidischer-algorithmus (translated)

https://www.whitman.edu/mathematics/higher_math_online/section03.03.html

https://en.wikipedia.org/wiki/Euclidean_algorithm

http://mathworld.wolfram.com/EuclideanAlgorithm.html

https://de.wikipedia.org/wiki/Euklidischer_Algorithmus (translated)

Pictures

I own all the pictures and they were uploaded on my imgur account. I used Microsoft Word 2013 and Paint to create them.

Example: https://i.imgur.com/59TeIXe.png?1