Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal expansion.

Question

Let I take n=8 ,or 7. Can any one illustrate me this defination clearly .

Comments

https://web.stanford.edu/class/archive/cs/cs103/cs103.1126/lectures/07/Slides07.pdf

Answer 1

Let $n$ be a positive integer.

Consider the $n+1$ integers $1, 11, 111, . . . , 11 . . . 1$ (where the last integer in this list is the integer with $n + 1$ $1$s in its decimal expansion).

Note that there are $n$ possible remainders when an integer is divided by $n$.

Because there are $n + 1$ integers in this list, by the pigeonhole principle there must be two with the same remainder when divided by $n$. The larger of these integers less the smaller one is a multiple of $n$, which has a decimal expansion consisting entirely of $0$s and $1$s.

For example, take $n = 7$

we have $1, 11, 111, 1111, 11111, 111111, 1111111 and\ 11111111$

The remainder possible when any number is divided by $7$ is $0, 1, 2, 3, 4, 5, 6$

These are the remainders when the numbers in the first list are divided by $7$:

$1\ \%\ 7 = 1$

$11\ \%\ 7 = 4$

$111\ \%\ 7 = 6$

$1111\ \%\ 7 = 5$

$11111\ \%\ 7 = 2$

$111111\ \%\ 7 = 0$

$1111111\ \%\ 7 = 1$

$11111111\ \%\ 7 = 4$

Now you can see that we have $7$ pigeonholes $\{ 0, 1, 2, 3, 4, 5, 6 \} $ and $8$ pigeons $\{ 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111 \} $, so there need to be at least one pigeonhole where $2$ pigeons will reside. 

In this case, we have $11\ \%\ 7 = 4$ and $11111111\ \%\ 7 = 4$

Their difference, i.e. $11111111 - 11 = 11111100$ is divisible by $7 (1587300 * 7 = 11111100)$

Hope this helps :)

reference : https://math.berkeley.edu/~arash/55/6_2.pdf

Comments

@srestha no..?:(

---

take a  number

suppose number is 1587300

Take a multiple of the number i.e. 7

Now, is this multiple makes the number that consists of 0's and 1's?

$1587300\times 7=11111100$ Yes :)

So, we got our desired result

It is simple thing

right?

---

111111  mod 7 = 0 → there is no need to subtract those 2 numbers. Right?

Answer 2

Example:

Pigeonhole can be applied for any number

Say n=4   And 5 (n+1) randomly taken numbers which are 7,21,26,55 and 57. if you divide any number with 4 then you can get remainder as 0,1,2,3 any of there. if we are taking 5 number which is more than 4 then it is possible at least two number on division with 4 have same remainder. This is the pigeonhole principle said.

Then,

         7%4=3

        21%4=1

         26%4=2

         55%4=3

         57%4=1

Here number 7 and 55 have same remainder as well as 21 and 57 have same remainder

So, if you subtract from big number to smaller number. you will get

                          55-7=48    48 is completely divisible by 4

                          57-21=36   36 is completely divisible by 4

Because,

                     (52+3=55)-(4+3=7)

again              52+3-4-3=48    // Remainder 3 is cancel out that's why we got subtraction is completely divisible by 4 .

        56+1-20-1=36   // Remainder 1 is cancel out that's why we got subtraction is completely divisible by 4 .

 

Comments

So here we get 48 and 36. How we can write decimal expansion of 48 and 36 that entirely consists of 0s and 1s?

Answer 3

Consider the sequence of numbers formed only with digit 1

S= { 1, 11, 111, 1111, 11111, 111111, .........}

Now, we know that a number n can have n remainders.

So, if we pick any (n+1) numbers from the the sequence S then by pegion hole principle we can say there must exist two numbers a and b among the chosen n+1 numbers such that a and b leave the same remainder when divided by n.

Hence the number (a-b) is divisible by n.

Now, the number (a-b) will consist of digits only 1 and 0.

Hence, for any number n there exist a multiple of n which will contain only 0's and 1's in its decimal expansion.