Any given number will divide into some combination of 3 and 0's

82 Views Asked by At

Now, I have to prove that any number could be made to divide into at least 1 arbitrary long sequence of 3's and 0's. That is, for any $n$ there always exist a number $x$ made up of 0's and 3's such that $ x\equiv 0 \pmod n$. The proof is supposed to be done by the pigeonhole principle but i can't seem to find it.

Any idea on how to solve it using any method?

1

There are 1 best solutions below

0
On

If there are more pigeons than holes, then there has to be a hole that contains more than one pigeon.

Note that to reach your conclusion, it is enough to show that you can find $x_1,x_2\in\mathbb{N}$ such that $x_1\equiv x_2\mod{n}$ in such a way that $x=x_1-x_2$ is of the form you want. As Lahtonen said in comment, working with numbers made up of $3$'s will help you out.

So, what should you consider as pigeons or holes in order to reach $x_1\equiv x_2\mod{n}$?