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

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\,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.

Tags:

Elementary Number Theory

Repunit Numbers

Related

Generating correlated random numbers: Why does Cholesky decomposition work? Little Rudin series convergence exercise If the series $\sum_0^\infty a_n$ converges, then so does $\sum_1^\infty \frac{\sqrt{a_n}}{n} $ Given number of trailing zeros in n!, find out the possible values of n. Polynomials and partitions Finding sum of factors of a number using prime factorization On a two dimensional grid is there a formula I can use to spiral coordinates in an outward pattern? A system of equations with 5 variables: $a+b+c+d+e=0$, $a^3+b^3+c^3+d^3+e^3=0$, $a^5+b^5+c^5+d^5+e^5=10$ How to determine if 2 points are on opposite sides of a line What Topology does a Straight Line in the Plane Inherit as a Subspace of $\mathbb{R_l} \times \mathbb{R}$ and of $\mathbb{R_l} \times \mathbb{R_l}$ Showing that the product and metric topology on $\mathbb{R}^n$ are equivalent The set of all finite sequences of members of a countable set is also countable

Recent Posts