More pigeons?

**billym** · November 5th 2009, 11:00 AM

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?

**Bacterius** · November 5th 2009, 10:43 PM

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.

**Defunkt** · November 6th 2009, 02:28 AM

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!

**Debsta** · November 6th 2009, 02:30 AM

Works in binary

**Bacterius** · November 6th 2009, 11:26 AM

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 ?

**clic-clac** · November 6th 2009, 02:24 PM

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<n$ 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)

**awkward** · November 6th 2009, 04:20 PM

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...

**clic-clac** · November 7th 2009, 12:50 AM

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

Thread: More pigeons?

LinkBack

Thread Tools

Display

More pigeons?

Reply

Reply

Search Tags