PDF chapter test TRY NOW

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

Important!

Two integers, \(a\) and \(b\), are said to be congruent to modulo \(m\), if they both receive the same remainder when divided by \(m\).