17
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ Either answer to this related question solves this easily. $\endgroup$ – Chris Eagle Jun 27 '12 at 14:12
  • 3
    $\begingroup$ @ChrisEagle: that question allows digits $0$, this one doesn't. $\endgroup$ – Marc van Leeuwen Jun 27 '12 at 14:13
  • 6
    $\begingroup$ @Marc: Yes, I know. However, my answer covers this case explicitly, while N. S.'s answer is easily extended to this case. $\endgroup$ – Chris Eagle Jun 27 '12 at 14:15
  • 2
    $\begingroup$ @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). $\endgroup$ – rschwieb Jun 27 '12 at 14:27
  • $\begingroup$ Off topic, but I think this prime factorization is a little neat. Doubtless there are more amazing ones but: $11111111111=21649\cdot 513239$ $\endgroup$ – rschwieb Jun 27 '12 at 18:22
28
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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

Let's do a simple example: $\rm\,n=9,\,$ with number $\rm\,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 $\rm\,9\mid\color{#c00}{4321\!-\!1} = \color{#0a0}{432}\cdot 10,\,$ so $\,9\,|\,\color{#0a0a}{432}.$

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

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.