Coding Club Of Competitive Programmers

  Euclid's GCD Algorithm One of the earliest known numerical algorithms is that developed by Euclid (the father of geometry) in about 300 B.C. for computing the greatest common divisor (GCD) of two positive integers. Let  GCD(x,y)  be the GCD of positive integers  x  and  y . If  x = y , then obviously GCD(x,y) = GCD(x,x) = x . Euclid's insight was to observe that, if  x > y , then GCD(x,y) = GCD(x-y,y) . Actually, this is easy to prove. Suppose that  d  is a divisor of both  x  and  y . Then there exist integers  q 1  and  q 2  such that  x = q 1 d  and  y = q 2 d . But then x - y = q 1 d - q 2 d = (q 1  - q 2 )d . Therefore  d  is also a divisor of  x-y . Using similar reasoning, one can show the converse, i.e., that any divisor of  x-y  and  y  is also a divisor of  x . Hence, the set of common divisors of  x  and  y  ...