Euclid’s division lemmaMinor theorem used in the proof of a larger theorem. is a fundamental principle in number theory that describes the division of two positive integers. For example, if we consider the expression it is clear that , so the quotient is 4 and the remainder is 1, which can be restated as .

More formally, Euclid’s division lemma states that for any two positive integers and , there exist unique integers and satisfying , where .^[1]

Repeated application of the lemma is one way to calculate the greatest common divisorLargest positive integer that divides each of the integers in a set without leaving a remainder. (gcd) of two integers, a process known as the Euclidian division algorithm, as in the following example to find the gcd of 207 and 60:

So 3 is the greatest common divisor of 207 and 60.