Tends to infinity

Only maths… nothing else

  • Recent Posts

  • Categories

  • Top Posts

  • My previous writings

  • Advertisements
  • March 2011
    M T W T F S S
    « Feb   Jun »
  • Enter your email address to follow this blog and receive notifications of new posts by email.

    Join 8 other followers

  • you are

    • 1,240 th visitors on this page

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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: