To prove there exists a particular format of multiple

Question

The prompt is to show that there exists a multiple of n that is of the form: $9 . . . 90 . . . 0$ where $n \in \Bbb{N}$.

The way I tried to solve the problem was to think of all the numbers that start with $9$ followed by $n$ digits, this can be $S_1 = \{9, 90, 91, ... , 99999...\}$, then all the numbers that begin with $9$, followed by n digits and $90$ somewhere between them, $S_2 = \{990, 9090, 9190, 9290, ..., 9...90...\}$. I quickly realized that this set can't be finite, there are $n$ such numbers in a set like this.

What if there's only 3 numbers between those numbers? like $9$_ _ _$90$ _ _ _ $0$?

Then we could have $9$$\underline{\Bbb{N}}$ $\underline{\Bbb{N}}$ $\underline{\Bbb{N}}$ $90$ $\underline{\Bbb{N}}$$\underline{\Bbb{N}}$ $\underline{\Bbb{N}}$$0$ such numbers which brings us back to an infinite set of numbers?

I'm not sure how to approach a problem like this, would appreciate any hint or solution.

Answer 1

Write $n=2^\alpha5^\beta m$, where $\gcd(m,10)=1$. By Euler's Theorem $$10^\gamma\equiv1\pmod m$$ for some $\gamma$ (specifically, $\gamma=\phi(m)$ will do it), so $$m\mid 10^\gamma-1\ ,$$ so $$n\mid(10^\gamma-1)10^{\max(\alpha,\beta)}=9\cdots90\cdots0\ ,$$ where there are $\gamma$ nines and $\max(\alpha,\beta)$ zeros.

Answer 2

Consider the $n+1$ numbers $$9,\,99,\,999,\ldots,\,\overbrace{99\cdots99}^{n+1\ \rm digits}\ .$$ Two of these must have the same remainder modulo $n$. Their difference is a multiple of $n$, and it has the form $$9\cdots90\cdots0\ .$$

Answer 3

Prove that there exists a multiple of n that is in the format of 9..90..0 where n∈N

$$ \overbrace{10^{k1}-10^{k2}}^{k1>k2\ \rm } = \overbrace{9}^{k1-k2\ \rm }\ldots\,\overbrace{90\cdots0}^{k2\ \rm }\ .$$

For example:

• $ 10^{1} - 10^0 = 10-1 = 9$

• $ 10^{2} - 10^1 = 100-10 = 90$

• $ 10^{3} - 10^2 = 1000-100 = 990$

• $ 10^{4} - 10^2 = 10000-100 = 9900$

• $ 10^{7} - 10^5 = 10000000-100000 = 9900000$

Where $k1>k2$ and $k1-k2$ will give you the sequence of $9.....90..0$

---

A = $\{10,100,1000,...,10^{n-1}\}$

B = $\{0,1,2,.....,{n-1}\}$

$|B| = n < |A| = n+1, f:A->B$

---

$f(x) = $ x mod n, so by the pigeonhole principle, there are $n|x1-x2$

$|x1-x2| = 9....90....0$