The Euclidean Algorithm

 Let  a ,b belongs integers except {0}

If  a = q*b + r , then GCD(a,b)=GCD(b,r) .

q: is called the quotient 

 r: is called the remainder