Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
Either answer to this related question solves this easily. –  Chris Eagle Jun 27 '12 at 14:12
2  
@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
show 3 more comments

5 Answers

up vote 24 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
See also here and here. –  Bill Dubuque Sep 30 '12 at 18:31
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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