Euclid’s Division Lemma: Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b. (It is a technique to compute the Highest Common Factor (HCF) of two given positive integers.)