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?

Results 1 to 8 of 8

- Nov 5th 2009, 11:00 AM #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?

- Nov 5th 2009, 10:43 PM #2
## Reply

**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 $\displaystyle n$ (an infinity) must contain infinitely many numbers composed of $\displaystyle 0$'s and $\displaystyle 1$'s. Because of**Theorem 2**, these numbers have at least one divisor, and since they are infinitely many, there is a probability of $\displaystyle 1$ that $\displaystyle n$ is a divisor of one of these numbers.

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

- Nov 6th 2009, 02:28 AM #3

- Joined
- Aug 2009
- From
- Israel
- Posts
- 976

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:

$\displaystyle \{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!

- Nov 6th 2009, 02:30 AM #4

- Joined
- Oct 2009
- From
- Brisbane
- Posts
- 898
- Thanks
- 200

- Nov 6th 2009, 11:26 AM #5

- Nov 6th 2009, 02:24 PM #6

- Joined
- Nov 2008
- From
- Paris
- Posts
- 354

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

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

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

- Nov 6th 2009, 04:20 PM #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...

- Nov 7th 2009, 12:50 AM #8

- Joined
- Nov 2008
- From
- Paris
- Posts
- 354