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 [latex]\frac{29}{7}[/latex] it is clear that [latex]4<\frac{29}{7}<5[/latex], so the quotient is 4 and the remainder is 1, which can be restated as [latex]\frac{29}{7}=4*7+1[/latex].
More formally, Euclid’s division lemma states that for any two positive integers [latex]a[/latex] and [latex]b[/latex], there exist unique integers [latex]q[/latex] and [latex]r[/latex] satisfying [latex]a = bq + r[/latex], where [latex]0 ≤ r < b[/latex].[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:
[latexpage]$ 207=3*{\large \textcircled{\small 60}}+{\large \textcircled{\small 27}} $
$ 60=2*{\large \textcircled{\small 27}}+{\large \textcircled{\small 6}} $
$ 27=4*{\large \textcircled{\small 6}}+{\large \textcircled{\small 3}} $
$ 6=2*{\large \textcircled{\small 3}}+0 $
So 3 is the greatest common divisor of 207 and 60.
