To explain the concept of Euclid’s algorithm lets star with a simple question that might really help you in understanding Euclid’s algorithm more clearly.
But first the notations:
a mod b ≡ c means a%b = c%b
a|b means a divides b i.e. b%a =0 or b = a*k where k is some constant
b%a=c means b = a*k+c where k and c are some constants k is known as quotient and c as remainder
Given two non-negative integers 
and 
.We define the greatest common divisor as the largest number that divides both And . “The greatest common divisor” is also known as “The highest common Factor”, and its common designation as gcd or hcf:
Now try answering the following question:
I need exactly 2 litres and later 4 litres of water and I have one 3litre and another 5 litres tank. Which don’t have any markings since I need exactly 2 litres of water estimations won’t work. I also have a unlimited water source so how to get exactly 2 litres and 4 litres of water?? What all other possible exact quantities of water can I get ??
Common Sense produces the answer and implicitly you use the very basis of Euclid’ algorithm.
Hints:
5-3 =2
5+3=8
2+1=3
5-1=4
I think that is a pretty decent hint… 
Now straight to the subject of the article after making you already implicitly apply the algorithm, if you solved the above mentioned problem.
Euclid’s Algorithm can be given as follows:
![{\ Rm gcd} (a, b) = \ cases {a, & {\ rm if} b = 0 \ cr {\ [...]](http://e-maxx.ru/tex2png/cache/b8e1571eb429ef8ef1c06bc060dec3e7.png)
But how to we get the above mentioned results lets try proving it:
say the gcd of a and b is k so by definition gcd of a and b is the greatest number k i.e less than or equal to the smallest of the two and satisfies k|a and also k|b
if k|a then clearly a=k*m1 and so also for k|b b =k*m2
if a>b then:
since a and b have a common multiple k hence k|a+b and k|a-b and k|b-a but we consider only positive values.
Few Properties:
1)gcd(n,1)=1
2)gcd(n,0)=n{since n divides zero and n also divides n}
3)gcd(a,b)=gcd(b,a-b) since if k|a and k|b the k|a-b
a=k*m1 and b=k*m2
a-b = k*(m1-m2):- so clearly since m1 and m2 are co-primes(as k is the gcd no-other factor in common) hence gcd(a,b)=gcd(b,a-b)
4)gcd(a,b)=gcd(b,a%b)-since k|a and k|b k|a%b but how??
a=k*m1 b=k*m2.
a%b = k*m1%k*m2 = k*m1-c*k*m2 (c is multiplied since a can be more than twice of b for eg: a=56 and b=4 hence 56%4 = 4*9 - 9*4*1 here c is 9)
hence a%b=k*(m1-c*m2)
which clearly shows that k|a%b. And since m1,m2 are co primes as we have already considered k to be the gcd. So m1 and m2 have no other factor in common.
Hence gcd of both pairs (a,a%b) and (b,a%b) is the same.
after certain operations this expression mentioned above takes form of either 1 or 2 depending on whether the two numbers are co-primes{have no divisors in common other than 1}
form 2 or 1 is taken as follows:
gcd(a,b)=gcd(b,a-b)=gcd(a-b,2b-a)=gcd(2b-a,2a-3b)=gcd(2a-3b,5b-3a)………gcd(k,0)/gcd(n,1).
by this we also see that k can also be expressed as a linear combination of a and b i.e.
k=ax+by
where x and y are some integral constants.
But how do we always end up getting 0 and the gcd finally??
Explained while proofing postulates 3 and 4.
Try proofing in terms of mathematics by the following hint.
as already shown ax+by takes the form of k
assume a’x+b’y is the term just before gcd i.e. gcd(a,b)=………=gcd(a’x+b’y,ax+by)=gcd(ax+by,(a’-a)x+(b’-b)y)this is nothing but gcd(k,0)
so a’=a and b’=b .
Code:
int gcd (int a, int b)
{
if (b == 0)
return a;
else
return gcd (b, a% b);
}
Least Common Multiple is the smallest number that can be divided by both a and b.
if lcm is l then it satisfies l%a==0 && l%b==0 but it’s the smallest number i.e. >a and > b. which is the lcm:-
Obviously lcm(a,b)=a*b/gcd(a,b)
if both a and b divide l then a|l and b|l
l=a*c1 and l=b*c2
now a=k*m1 and b=k*m2*c2
so l=k*m1*c1 and l= k*m2*c2
so the least common multiple is the one having k as one divisor for it to be least result is:a*b/gcd(a,b)
k*k*m1*m2 now clearly least number having k*m1 and k*m2 as divisors is the LCM and least possible such number is k*m1*m2 which is the proposed LCM.
Hence lcm(a,b)=a*b/gcd(a,b).
int lcm (int a, int b)
{
return a*b/gcd (a, b) ;
}
//Since k(gcd(a,b)) can also be written as linear combination of a and b
//i.e k=ax+by we can even find x and y by the following code:
int gcdwl(int a, int b, int & x, int & y)
{
if (a == 0)
{
x = 0; y = 1;
return b;
}
int xa, yb;
int d = gcdwl(b% a, a, xa, yb);
x = yb - (b / a) * xa;
y = xa;
return d;
}
//try proofing the correctness of the above code hint:-gcd(a,b)=gcd(b,a%b)
//and gcd(a,b)=ax+by and also gcd(b,a%b)= bx1 + (a%b)y1
