3. Connecting Euclid's division lemma and modular arithmetic

Let $a$ and $b$ be two integers, where $a$ and $b$ are positive integers. Then, by Euclid's division lemma, we know that $a = bq + r$ where $0 \leq r < b$ and $q$ are integers. Now, let us apply the congruence modulo and for the given Euclid's division lemma.

 

Thus, from the given, we can say that $a$ is congruent to $r$ modulo $b$, for some integer $q$.

 

That is, $a = bq + r$

 

$a - r = br$

 

$a - r \equiv 0 (mod \ b)$

 

$a \equiv r (mod \ b)$

 

Therefore, using Euclid's division lemma, the equation $a = bq + r$ can be written as $a \equiv r (mod \ b)$.