19

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

J. W. Tanner
  • 58,836
  • 3
  • 38
  • 78
Eight
  • 725
  • 2
  • 9
  • 16
  • 4
    Either answer to [this related question](http://math.stackexchange.com/questions/83932/proof-that-a-natural-number-multiplied-by-some-integer-results-in-a-number-with) solves this easily. – Chris Eagle Jun 27 '12 at 14:12
  • 3
    @ChrisEagle: that question allows digits $0$, this one doesn't. – Marc van Leeuwen Jun 27 '12 at 14:13
  • 6
    @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
  • 2
    @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
  • even more, amount of 1th should be less or equal to number:) – varela Jun 27 '12 at 19:21
  • [More generalized version is here][1] [1]: http://math.stackexchange.com/questions/165160/all-odd-primes-except-5-divide-a-number-made-up-of-all-1s/165690#165690 – lab bhattacharjee Jul 02 '12 at 13:59
  • [A more generalized solution for any number in any base is here][1] [1]: http://math.stackexchange.com/questions/165160/all-odd-primes-except-5-divide-a-number-made-up-of-all-1s/165690#165690 – lab bhattacharjee Jul 02 '12 at 14:01

5 Answers5

30

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.

Cocopuffs
  • 10,199
  • 28
  • 41
18

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.

marlu
  • 13,444
  • 1
  • 39
  • 52
15

We can prove more very simply: if $\,n\,$ is coprime to $10\,$ then any number with $\, n\,$ digits all $\ne 0$ has a contiguous digit subsequence that forms a number divisible by $\,n.\,$ Suppose the digits are $\,d_{n}\ldots d_1.\,$ By $\,d_i\ne 0\,$ the $\,n\!+\!1\,$ numbers $\,0,\,d_1,\, d_2 d_1,\, d_3 d_2 d_1,\, \ldots,d_n\!\ldots d_1$ are distinct. By Pigeonhole $\rm\color{#c00}{two\ are\ congruent}$ $\!\bmod n,\,$ so $\,n\,$ divides their difference $ = 10^k\,$ times the number $\,\color{#0a0}{e\ne 0}\,$ formed by the $\rm\color{#0a0}{extra\ digits}$ of the longest, so $\,n\,|\,10^ke\,$ $\Rightarrow$ $\,n\mid e,\,$ by $\,n\,$ is coprime to $10$ and Euclid's Lemma.

Let's do a simple example: $\,n=9,\,$ with number $\,98765\color{#0a0}{432}1.\,$ Initial digit substrings $\!\bmod 9\,$ are
$$\begin{align}\bmod 9\!:\quad\ \ \color{#C00}{1}&\equiv\color{#c00}1\\ 21&\equiv 3\\ 321&\equiv 6\\ \color{#C00}{4321}&\equiv\color{#c00} 1\end{align}\qquad$$

therefore we conclude that $\,9\mid\color{#c00}{4321\!-\!1} = \color{#0a0}{432}\cdot 10,\,$ so $\,9\,|\,\color{#0a0a}{432}.$

In OP the divisor $\,n=10k+3\,$ is coprime to $10$, so the number $\,11\ldots 11$ $\,(n$ digits) does the trick, i.e. some digit subsequence $\color{#0a0}{11\ldots 11}$ forms an integer divisible by $\,n.$

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

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
  • See also [here](http://math.stackexchange.com/a/165163/242) and [here.](http://math.stackexchange.com/a/229273/242) – Bill Dubuque Sep 30 '12 at 18:31
3

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

Marc van Leeuwen
  • 111,890
  • 8
  • 161
  • 330
2

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

lab bhattacharjee
  • 1
  • 18
  • 201
  • 317