is divisible by . Note ¾ When a positive integer is divided by n , then the possible remainders are , , , . . .
, n - . ¾ Thus, when we work with modulo n , we replace all the numbers by their remainders upon division by n , given by , , , ,..., n - . Two illustrations are provided to understand modulo concept more clearly. Illustration To find (mod ) With a modulus of (since the possible remainders are , , , ) we make a diagram like a clock with numbers , , , .
We start at and go through numbers in a clockwise sequence , , , , , , , . After doing so cyclically, we end at . Therefore, º (mod ) Illustration To find - (mod ) With a modulus of (since the possible remainders are , , ) we make a diagram like a clock with numbers , , . We start at and go through numbers in anti-clockwise sequence , , , , .
After doing so cyclically, we end at . Therefore, −≡ (mod ) . . Connecting Euclid’s Division lemma and Modular Arithmetic Let m and n be integers, where m is positive.
Then by Euclid’s division lemma, we can write n mq where ≤ < m and q is an integer. Instead of writing n mq we can use the congruence notation in the following way. We say that n is congruent to r modulo m , if n mq for some integer q . n = mq n – r = mq n – r º (mod m ) n º r (mod m ) Thus the equation n mq through Euclid’s Division lemma can also be written as n º (mod m ).
Fig. . Progress Check . Two integers a and b are congruent modulo n if .
. The set of all positive integers which leave remainder when divided by are . Fig. .