Euclid's Division Lemma states that for any two positive integers a and b, there exist unique integers q and r such that a = bq + r, where

Euclid's division lemma :


Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b

1