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:

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