GCD - The Euclidean Algorithm

If you have weak mathematics background, it comes into the disadvantage when you started learning GCD in the class. Many people could not understand it well. It involves some assumptions and theory proofings that makes students more confusing. You should not give up. This is going to be tested in your exam and therefore, you really need to understand GCD.

GCD in simply explanation

It is the largest number that can divide 2 numbers (n and m) and it is denoted by gcd(n,m).

- Imagine if you want to divide 2 numbers: one is 8 and another one is 12. What will be the largest number to divide? As you know, the number (2) or (4) both can divide and the number (4) will be the GCD since it is the largest number. Therefore, gcd(8,12)=4


Algorithm
1. Write 2 numbers.
2. Reduce the larger number (by subtracting smaller number)
3. Repeat step 2 until one of the number become zero.
4. Voila.. you get the gcd.
(can't imagine the picture.. see below)


I am now going to draw some analysis. If you look at the picture above carefully, in each step, both number M & N are newly formed by adding some multiple of original numbers. For example, in step 4, the new number for N becomes 12 by adding (negative 5 times of M value).

In this case, we can say that there are some numbers like a & b, such that gcd(n,m) = a*n + b*m.