Euclid’s division lemma states that for any positive integers a and b, there exist unique integers q and r such that a = bq + r, where r must satisfy (a) 1 ˂ r ˂ v (b) 0 ˂ r ≤ b (c) 0 ≤ r ˂ b (d) 0 ˂ r ˂ b