EUCLIDS ALGORITHM FROM ALL PRESPECTIVES


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 a and b .We define the greatest common divisor as the largest number that divides both a And b . “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 {\ [...]
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

Euler’s Function


Well lets first discuss the Euler function.
The Euler function of a number n. denoted by E(n) throughout the writeup.
E(n) tells us the number of numbers less than or equal to n that are co-prime with the  given number n.
a mod b is congruent with c means a%b = c%b. and is denoted by a mod b≡c. Meaning a mod b is congruent with c.
Two integral numbers  a and b are said to be co-prime or relatively prime if they have only 1 as a common divisor  i.e.  if their GCD/HCF  is 1

c|a means c divides a

For a prime number p:

1)E(1)=1:-Pretty evident from  the definitions above

2)E(p)=p-1 :-this is pretty obvious a number p is co-prime  to all number [1,p-1]. p is not co-prime with p but clearly 1 is co-prime with p from definition of co-prime. So the result is pretty  evident.

3)If p is a prime number then E(p^a)=(p^(a-1))*(p-1) or (p^a)-(p^(a-1)):-This is not that obvious but how do  we get it. Before looking down try to stress your brains to think how this is possible??

If u have given up then u can proof it as follows:
since p was prime so the only numbers co-prime  to  p^a  and less than equal to p are p,p*2,p*3,p*4……p*p^(a-1)=F(say)
and hence the total number of numbers that are co-prime with p^a = number of numbers less than or equal to  p^a(=p^a) – number of  numbers that are not co-prime with p^a.

As already shown in F the number of co-primes to  p^a are  p^(a-1) hence the value of E(p^a)=p^a-p^(a-1)

4)If a and b are co-primes then E(a*b)=E(a)*E(b):- Even this is not that obvious So let’s even proof this.
Consider E(a)=x and E(b)=y
clearly x=a – number of numbers not co-prime to a. And
clearly y=b – number of numbers not co-prime to b.

Where no elements in the set {number of numbers co-prime to  a} and {number of numbers co-prime to b} overlap since they are co-prime.

now lets consider a= pa1^ca1*pa2^ca2*pa3^ca3…..pan^can{we know all numbers can be expressed as powers of prime numbers}
similarly b can also be written as b=pb1^cb1*pb2^cb2*pb3^cb3…..pbn^cbn{no elements of {pb1,pb2,pb3….pbn} and {pa1,pa2,pa3….pan} overlap since both are co-prime}
numbers that are not co-prime
So E(ab)=ab -{co-primes to ab}(this is nothing put  (co-primes to a)*b + (co-primes to b)*a – ((co-primes to a)*(co-primes to b))
which gives us E(ab) = E(a)*E(b)
But how are divisor of ab equal to that given??

co-prime to a are (pa1,2*pa1,3*pa1……,a),(pa2,2*pa2,3*pa2…….a),…….(pan,2*pan,…..a)

co-prime to b are (pb1,2*pb1,3*pb1……,b),(pb2,2*pb2,3*pb2…….b),…….(pbn,2*pbn,…..b)

Numbers  co-prime to a are =a/pa1 + a/pa2…….. + a/pan (A say)

Numbers  co-prime to a are =b/pb1 + b/pb2…….. + b/pbn (B say)

co-prime to ab are: (pa1,2*pa1,3*pa1……,ab),(pa2,2*pa2,3*pa2…….ab),…….(pan,2*pan,…..ab) +  (pb1,2*pb1,3*pb1……,ab),(pb2,2*pb2,3*pb2…….ab),…….(pbn,2*pbn,…..ab)

so E( a)=a-(a/pa1+a/pa2+a/pa3+….a/pan)
and  E(b) = b-(b/pb1 + b/pb2 + b/pb3 + …b/pbn)

E(a)*E(b) = ab + A*B -b*A – a*B//as listed earlier

Hence Numbers  co-prime to ab are: ab/pa1 +ab/pa2+……ab/pan + ab/pb1 + ab/pb2 + ……….ab/pbn (Say this is  m)
Hence E(ab) = ab- m
m can be written as b*(numbers co-prime to a) + a*(numbers co-prime to b) – common terms in the above expression

Now to find the common terms:
If anyone doubts that there will be any common term or not lets take an example a=9 and b=10
a and b are co primes so:
numbers not co-prime to 9 are 3,9 and 2,5,10 for 10
A=2 and B=3
E(a)=7
E(b)=7
E(ab)= 90 + 6 -20 -27 =49 which is same as E(a)*E(b) =7*7

But  A*B elements are being counted twice but how??
This will be discussed under Chinese remainder theorem. But u already have the data try proving it yourself before trying the  Chinese remainder theorem proof. It would help better in understanding the theorem.

5) As discussed earlier every number can be expressed as powers of prime numbers so for a number n that can be expressed as n = p1^a1*p2^a2*p3^a3…..pk^ck
E(n)=n(1-1/p1)(1-1/p2)(1-1/p3)….pk^ck(1-1/pk)
But how??
by property 4 we know we can express:
E(n) as E(n)=E(p1^a1)*E(p2^a2)*E(p3^a3)*…..E(pk^ck) :- This holds since all prime numbers are co-primes with all other numbers.
now using theorem 3:
E(n)=(p1^a1-p1^(a1-1))*(p2^a2-p2^(a2-1))*(p3^a3-p3^(a3-1))*….(pk^ak-pk^(ak-1))
which gives:
(p1^a1(1-1/p1))*(p2^a2(1-1/p2))*(p3^a3(1-1/p3))*…….(pk^ak(1-1/pk))
we know n=p1^a1*p2^a2*p3^a3…..pk^ck
hence we get  E(n) = n*(1-1/p1)*(1-1/p2)*(1-1/p3)*….(1-1/pk)

Now we can easily write the program to calculate the Euler function for a number n:

int E(int n)
{
	 int answer = n;
	 for (int i = 2; (int)pow(i/1.0,2.0) <= n; + + i)
		 if (n% i == 0)
                 {
			 while (n% i == 0)
				 n / = i;
			 result = result - result / i;
		 }
	 if (n> 1)
		 result - = result / n;
	 return result;
 }

Hello world!


Well to introduce the blog I am starting off  to keep track of my activities i.e. to see how I progressed between the days to be what i would be 20 years down the line. Since I am occupied by ACM-ICPC rite now my following posts would contain whatever I learn in my  path towards achieving my dream. I do have a superficial knowledge about the important topics that need to be covered for being among the very best. So I present to you and myself the various topics I am covering to prepare for it. This would also help me to revise stuff. So I am also helping myself in a way. I know I could have used FB notes, but then my mistakes won’t be caught and neither would i be be to help others through my in-dept analysis. So I’ll pick topics,solve Spoj and Codeforces questions and post them out here  the course of this blog till the regionals. Have a nice day!!
I would be covering the following topics not exactly in the order as mentioned:

1)Simulation for problem solving
2)Segment or Interval trees
3)Tries
4)Dynamic Programming
5)Greedy Approach
6) Dynamic + Greedy
7)Linear Programming
8)BFS and DFS
9)Graph Algorithms
10)Number Theory
11)Graph Theory
12)Some Numerical Methods
13)All Important and less solved questions from SPOJ