## Congruence modulo

Posted by tendstoinfinity on March 15, 2011

Recall that (mod m) when a – b is divisible by m. Another way to understand this a and b leaves same remainder when divided by m. We have learnt that this relation is equivalent relation. So we can write

If (mod m) and (mod m) then (mod m). (transitivity). Actually congruence modulo m splits the set of natural number in m distinct classes. Those are classes of remainders 0,1,2,…n-1.

you can surely prove this. There are some more interesting relations and more interesting uses of congruence.

- (mod m) and (mod m) then (mod m).
- (mod m) and (mod m) then (mod m). we can prove this by noting ac – bd = ac – bc + bc – bd = c(a-b) + b(c -d). both the bracketed expressions are divisible by m.

one special case of this is

- (mod m) and n is any natural number then (mod m)

Some applications of the above results

**What will be the remainder if is divided by 7**

Since (mod 7) so (mod 7) that is (mod 7). therefore leaves remainder same as that of 1 when divided by 7. Which is clearly 1

**Prove that + is divisible by 31.**

Since (mod 31) so (mod 31) and (mod 31) so (mod 31)

therefore (mod31) . hence the result.(when anything leaves remainder 0 it is divisible by the given)

You can do a lot of interesting findings with the help of congruence modulo, divisibility tests are surely an important class.

Before discussion of divisibility tests we introduce a notation taken from the book *‘Elementary Mathematics*‘ by **G. Dorofeev, M. Potapov and N.Rozov** (originally published by MIR publishers, in India CBS publishes this book)

=

**Divisibility by 2, 5 and 10**

Any natural number is congruent to its last digit modulo 2(5 or 10) for

= + but 10 is divisible by 2(or 5 or 10) so

(mod 2). The number itself will have same remainder as that of last digit when divided by 2 , similar result for 5 or 10

**Divisibility by 4 and 8**

you can prove similarly (mod 4).

and (mod 8).

so any number leaves a remainder same as that of the last two digits when divided by 4, and of the last three digits when divided by 8.

I will share divisibility test by 3,7,9,11,13 in my later posts.

## Leave a Reply