# Math Help - More pigeons?

1. ## More pigeons?

Surely this is a basic problem. I have no idea how to start.

"n is any positive integer. Show that there is a positive integer k which is a multiple of n which consists entirely of 1's and 0's."

I have no idea how to start. Can somebody kick me?

Theorem 1 : A non-zero number has infinitely many multiples.
Theorem 2 : A non-zero number has at least one divisor.
Theorem 3 : There are infinitely many numbers.

Therefore, according to Theorems 1 & 3, the set of all multiples of $n$ (an infinity) must contain infinitely many numbers composed of $0$'s and $1$'s. Because of Theorem 2, these numbers have at least one divisor, and since they are infinitely many, there is a probability of $1$ that $n$ is a divisor of one of these numbers.

I don't know if this is "mathematically" correct, though.

3. Originally Posted by Bacterius
Theorem 1 : A non-zero number has infinitely many multiples.
Theorem 2 : A non-zero number has at least one divisor.
Theorem 3 : There are infinitely many numbers.

Therefore, according to Theorems 1 & 3, the set of all multiples of $n$ (an infinity) must contain infinitely many numbers composed of $0$'s and $1$'s. Because of Theorem 2, these numbers have at least one divisor, and since they are infinitely many, there is a probability of $1$ that $n$ is a divisor of one of these numbers.

I don't know if this is "mathematically" correct, though.
Both of these statements are wrong. The fact that a number has infinite integer multiples does not necessarily mean one of those integers will consist of the digits 0,1. Using the same logic we could reach the false conclusion that every positive integer has a multiple which consists solely of the digits 7,1 - which is not true.

Also, the multiples of n are divided by it because, well, they are multiples of it (this is how you defined them)... However, the fact that they are infinite does not necessarily mean n will divide one of them. Take, for example, the following infinite sequence of multiples:

$\{a_n\}_{n=1}^{\infty} : \ a_i = 7^i \ \forall i \geq 1$

Then this is an infinite sequence of multiples of seven, but none of them are divided by 5!

4. Works in binary

This is why I said I wasn't sure it worked mathematically. It doesn't, yet those type of questions can get hard sometimes, eh ?

6. An integer consisting in only 0's and 1's is a sum of $10^k,$ for some $k\in\mathbb{N}.$ Let $n$ be a positive integer,

we want to prove there are integers $k_1,...,k_m$ such that $\sum\limits_{i=1}^m10^{k_i}=0\mod n.$

For all $k\in\mathbb{N},$ there is an $0\leq i such that $i\equiv 10^k\mod n.$ What if we consider these $i$ for $0\leq k\leq n^{n-1}$ (here come the pigeons)

7. I think this may be equivalent to clic-clac's hint (I'm not sure), but here is another approach anyway:

Consider the n+1 integers 1, 11, 111, ..., on up to n+1 repetitions of 1.
There are n congruence classes modulo n, so at least two of these integers must be in the same congruence class. Then...

8. I don't think it is equivalent, your way is just far prettier and easier than mine!