Euclid's Division Algorithm
Check us out at http://www.tutorvista.com//videos The division algorithm is a theorem in mathematics which precisely expresses the outcome of the usual process of division of integers. Its name is a partial misnomer: it is not a true algorithm (a well-defined procedure for achieving a specific task), but it can be used to find the greatest common divisor of two integers. The term "division algorithm" is also used in algebra for a general variant of this theorem, shown to hold in integral domains which are principal ideal domains. Consider the set We claim that S contains at least one nonnegative integer. There are two cases to consider. •If a is nonnegative, then choose n = 0. •If a is negative, then choose n = ad.