# Prove that every number ending in a $3$ has a multiple which consists only of ones.

Prove that every number ending in a $3$ has a multiple which consists only of ones.

Eg. $3$ has $111$, $13$ has $111111$.

Also, is their any direct way (without repetitive multiplication and checking) of obtaining such multiple of any given number( ending with $3$) ?

• Either answer to this related question solves this easily. – Chris Eagle Jun 27 '12 at 14:12
• @ChrisEagle: that question allows digits $0$, this one doesn't. – Marc van Leeuwen Jun 27 '12 at 14:13
• @Marc: Yes, I know. However, my answer covers this case explicitly, while N. S.'s answer is easily extended to this case. – Chris Eagle Jun 27 '12 at 14:15
• @MarcvanLeeuwen After arranging a multiple which has all ones followed by all zeros, you may divide through by 10 as many times as you like to remove the zeros (since a number ending in 3 is coprime with 2 and 5). – rschwieb Jun 27 '12 at 14:27
• Off topic, but I think this prime factorization is a little neat. Doubtless there are more amazing ones but: $11111111111=21649\cdot 513239$ – rschwieb Jun 27 '12 at 18:22

The number $111...11$ with $n+1$ digits is $1 + 10 + ... + 10^n = \frac{10^{n+1} - 1}{9}$ using the formula for geometric progressions.

Now any number $x$ which ends in three is coprime to $10$, and so is $9x$: $10$ is a unit $\mod 9x$. In particular, you have the Euler-Fermat theorem: $10^{\varphi(9x)} \equiv 1 \mod 9x$. This means that $9x$ divides $10^{\varphi(9x)} - 1$, so $x$ divides $\frac{10^{\varphi(9x)} - 1}{9}$.

So $x$ divides the number $111..11$ with $\varphi(9x)$ digits, where $\varphi$ is Euler's phi function.

If $n$ ends with a $3$ it must be coprime to $10$. Then, by Fermat's little theorem, $$10^{\varphi(9n)} \equiv 1 \pmod {9n},$$ so $n$ divides $(10^{\varphi(9n)}-1)/9$ whose decimal representation consists only of ones.

We can prove more very simply: if $\rm\:m\:$ is coprime to $10\,$ then any number with $\rm\: m\:$ digits all $\ne 0$ has a contiguous digit subsequence that forms a number divisible by $\rm\:m.\:$ Suppose the digits are $\rm\:d_{m}\ldots d_1.\:$ By $\rm\,d_i\ne 0\:$ the $\rm\:m\!+\!1\:$ numbers $\rm\:0,\,d_1,\, d_2 d_1,\, d_3 d_2 d_1,\, \ldots,d_m\!\ldots d_1$ are distinct. By Pigeonhole two are congruent $\rm\:mod\ m,\:$ so $\rm\:m\:$ divides their difference $\rm = 10^k\:$ times the number $\rm\,n\ne 0\,$ formed by the extra digits of the longest, so $\rm\:m\,|\,10^kn\:$ $\Rightarrow$ $\rm\:m\:|\:n,\:$ by $\rm\:m\:$ is coprime to $10.\:$

Let's do a simple example. Let $\rm\:m=9,\:$ and let the number be $\rm\:98765\color{green}{432}1.\:$ Modulo $9$ we have $\rm\:1 \equiv\color{#C00} 1,\ 21\equiv 3,\ 321\equiv 6,\ 4321\equiv\color{#C00} 1,\:$ so $\rm\:9\:|\:4321\!-\!1 = 432\cdot 10,\:$ so $\,9\,|\,\color{green}{432}.$

In your case, the divisor $\rm\:m\:$ is coprime to $10$, hence the number $\,11\ldots 11$ $\rm\,(m$ digits) does the trick, i.e. some subsequence $11\ldots 11$ is divisible by $\rm\:m.$

The result extends to any number having $\rm\:m\:$ nonzero digits: simply take the subsequences beginning with nonzero leading digit. This implies that the $\rm\:m+1\:$ numbers are increasing (so distinct), and the number formed by the extra digits is nonzero, since its leading digit is nonzero.

Call your number $n$. Since $9n$ is relatively prime with $10$, the number $10$ is invertible modulo $9n$, so there is some power $10^k$ (with in fact $k$ a divisor of $\phi(9n)$) that is congruent to $1$ modulo $9n$, in other words $9n$ divides $10^k-1$, a number formed of $k$ digits $9$. But then $n$ divides the number with $k$ digits $1$.

Find a more generalized solution for any natural number in base here: All odd primes except $5$ divide a number made up of all $1$s