# Tends to infinity

• ## Follow Blog via Email

Join 8 other followers

# Archive for the ‘Uncategorized’ 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.

## salesman problem

Posted by tendstoinfinity on February 10, 2011

pichak@scientist.com

Perhaps you have remembered Dr. A N Mishra, KV Jorhat one of the teachers blessed with splendid presence of mind. He has asked me a very beautiful question.

One salesman used to carry 40 different weights 1kg,2kg,….40kg for weighing articles upto 40kgs, until somebody suggested why doesn’t he use less number of weights so that he can weigh all the kgs upto 40kg in one turn. Now can you help the salesman to choose minimum number of weights in the following cases

i. weights can be placed on either of the  pans of the balance.(this is Dr. Mishra’s question)

ii. weights can be placed only on left pan and object on right pan.( this is my variation)

before presenting the solutions directlyI want to see the Result: All the naturals up to $2^{n+1}-1$ can  be obtained by adding all or some of the element of the set  {1=20,21,22,23,…2n}    only once. (Why?) For example by adding some or all of the set only once you can get all naturals upto 7 using all or some {1,2,4}. You can see following table for illustaration

 No of 4 No of 2 No of 1 sum 0 0 1 1 0 1 0 2 0 1 1 3 1 0 0 4 *1 0 1 5* #1 1 0 6 1 1 1 7

Are you able to see that in the above table (no of 4,no of 2 and no of 1) form the binary ( number system of base 2)representation of the respective sum. *Just as (101)2 =(5)10 . Now binary representation of 8 to 15 =24-1 contains 4digits. So the sum of any natural number from 1 to 15 can be represented as a sum of all or some of {20=1, 2, 4, 8=23} only once. I think my variation i.e (ii) can now be  solved. Because you can only use one pan to place weights so addition only should be used so 6 weights of {1,2,4,8,16,32} will be necessary for  25-1<40<26-1. In fact the salesman can weigh any weights upto 61kg in one turn using these weights.

Another approach of   thinking

There are two places for the weight units either in the balance pan or in bag of salesman. Let 0 represents the bag and 1 represents pan so weighing a weight of 6kg we have representation 110# means 4kg, 2kg on the pan and  1 kg in the bag.

Before we turn to Dr. Mishra’s problem we want to see the a wonderful property of ternary system(number system of base 3) : every natural can be represented as the sum or difference of two numbers whose ternary representation contain only 0’s and 1’s or otherwise every natural can be expressed as the sum or differences of numbers of the form 3n(n is a natural no.). If the natural number is a power of 3(of the form 3n) the prove is obvious. Now for the other case see the following example

(4)10=(11)3=(11)3-03 = 31+30

(5)10= (12)3

= 1.31+2.30

= 1.3+(3-1)30

= 1.3+3-1

=2.3-1

=(3-1)3-1

=32-31-30

= (100)3-(10)3-10

I hope you can generalize the facts.

So every natural number upto  $\frac{3^{n+1}-1}{2}$can be expressed by adding or subtracting all or some elements of the set {1=30,31,32,…3n}

So every number less than 40 can be expressed as sum or difference of all or some of {1,3,9,27}. These are weights required by the salesman.

For base 4, Similarly every natural number can be expressed by sum or difference of the powers of 4 taking any specific element not more than twice.

5 = 41+40

6 = 4+1+1 (1 =40)

7 = 16 – 4 – 4 – 1

53 = 64 – 16 + 4 +1

Its proof is  so simple. But giving a little time you can prove it.

Hopefully in some post I will discuss some more interesting fact of the bases of number system.

Posted in Recreational, Uncategorized | 3 Comments »

## A SPECIAL YEAR 2011

Posted by tendstoinfinity on January 13, 2011

I recently came across  Prof. Gary E. Davis‘s blog Republic of mathematics. He pointed out 2011 is itself a prime number and it can be represented as the sum of 11 consecutive prime numbers.

2011=157+163+167+173+179+181+191+193+197+199+211

or sum of 3 consecutiprime numbers 2011 = 661+673+677

The next year after 2011 that is a prime number and a sum of consecutive prime numbers is 2027 = 29+31+37+41+43+47+53+59+61+67+71+73+

79+83+89+97+101+103+107+109+113+127+131+137+139

but that year is not a sum of a prime number of consecutive prime numbers.

However, 2027 does have the curious and interesting property that it is prime and the sum of its digits 2+0+2+7=11 is also a prime number. It is the first year after 2003 that has this property.

The next year that is a prime number and a sum of a prime number of consecutive prime numbers is 2081 =401+409+419+421+431.

I am testing whether the things works or not $lim_{x\mapsto a} =\inftyx$