# Tends to infinity

• ## Follow Blog via Email

Join 8 other followers

# Archive for the ‘Number theory’ Category

## Congruence modulo

Posted by tendstoinfinity on March 15, 2011

Recall that  $a \equiv\ b$(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  $a \equiv\ b$(mod m) and $b \equiv\ c$(mod m) then $a \equiv\ c$(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.

• $a \equiv\ b$(mod m) and $c \equiv\ d$(mod m) then $a+c \equiv\ b+d$(mod m).
• $a \equiv\ b$(mod m) and $c \equiv\ d$(mod m) then $ac \equiv\ bd$(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

• $a \equiv\ b$(mod m) and n is any natural number then $a^{n} \equiv\ b^{n}$(mod m)

Some applications of the above results

What will be the remainder if $6^{100}$ is divided by 7

Since $6 \equiv\ (-1)$(mod 7) so $6^{100} \equiv\ (-1)^{100}$(mod 7) that is $6^{100} \equiv\ 1$(mod 7). therefore $6^{100}$ leaves remainder same as that of 1 when divided by 7. Which is clearly 1

Prove that $30^{99}$$61^{100}$ is divisible by 31.

Since $30 \equiv\ (-1)$(mod 31) so $30^{99} \equiv\ (-1)$(mod 31) and $61 \equiv\ (-1)$(mod 31) so  $61^{100} \equiv\ 1$(mod 31)

therefore $30^{99}+ 61^{100}\equiv\ 0$ (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)

$\overline{a_{1}a_{2}a_{3}...a_{n}}$ = $a_{1}.10^{n}+a_{2}.10^{n-1}+a_{3}.10^{n-2}+...+a_{n}.10^{0}$

Divisibility by 2, 5 and 10

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

$\overline{a_{1}a_{2}a_{3}...a_{n}}$$\overline{a_{1}a_{2}a_{3}...a_{n-1}}.10$+$a_{n}$ but 10 is divisible by 2(or 5 or 10) so

$\overline{a_{1}a_{2}a_{3}...a_{n}} \equiv\ a_{n}$(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 $\overline{a_{1}a_{2}a_{3}...a_{n}} \equiv\overline {a_{n-1}a_{n}}$ (mod 4).

and $\overline{a_{1}a_{2}a_{3}...a_{n}} \equiv\overline{a_{n-2}a_{n-1}a_{n}}$(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.