PUMPA - THE SMART LEARNING APP

Helps you to prepare for any school test or exam

Download now on Google PlayLet \(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\).