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)\).