>>15000412To find the greatest common divisor ( gcd(a,b) ) of a number you can solve a series of equations.
the greatest common divisor is the largest numbers that divides a and divides . For instance
the gcd(12,10) = 2 because 2 is the common factor 12 and 10.
Euclids algorithm looks like this
gcd(a,b) , let a > b , then solve these equations
a = b(q1) + r1
b = r1(q2) + r2
r1 = r2(q3) + r3
r2 = r3(q4) + r4
...
r_{n-2} = r_{n-1} (qn) + r_n
r_{n-1} = q_{n+1} r_n + r_{n+1} (r_{n+1} = 0)
If you do this then the greatest common divisor will be equal to the last non 0 remainder
Here is an example
gcd(108,42)
108 = 42 * 2 + 24
42 = 24 * 1 + 18
24 = 18 * 1 + 6
18 = 6 * 3 + 0.
We got to the end so that means the greatest common divisor of 108 and 42 is 6.
