1
$\begingroup$

Prove that for every positive integer $n$ coprime to $10$ there exists a multiple of $n$ that does not contain the digit $1$ in its decimal representation.

I thought about using Euler's Totient Theorem. This says that $a^{\phi(10)} \equiv 1 \pmod{10}$. How could we continue from this?

$\endgroup$
3
$\begingroup$

It is more fruitful considering that $10^{\phi(a)}\equiv 1\pmod a$.

Then $10^{\phi(a)}-1$ is a multiple of $a$ and it has only nines in its decimal representation.

$\endgroup$
1
$\begingroup$

Consider numbers $3,33,333,3333,...,\underbrace{333\ldots 3}_\text{n 3's}$
Then say $3\equiv r_1\pmod n$,$33\equiv r_2\pmod n$,$\underbrace{333\ldots 3}_\text{n 3's}\equiv r_n\pmod n$.
If any of $r_i$ is $0$ then we're done if not then there exist $r_i,r_j$ and say i>j that are equal from pignhole principal say
$$r_i\equiv r_j\pmod n$$ or $$\underbrace{333\ldots 3}_\text{i 3's}\equiv \underbrace{333\ldots 3}_\text{j 3's} \pmod n$$ then $$\underbrace{333\ldots 3}_\text{i-j 3's}\underbrace{00\ldots 0}_\text{j 3's}\equiv 0\pmod n$$Since $(n,10)=1$ then $$\underbrace{333\ldots 3}_\text{i-j 3's}\equiv 0 \pmod n$$ And we are done

$\endgroup$
1
$\begingroup$

The set of multiples of $n$ is a subset of $\mathbb{Z}$ with positive density, while the set $E$ of numbers without $1$s in their decimal representation is rather sparse (it is an integer Cantor set with zero density), so there is for sure a multiple of $n$ in $\mathbb{N}\setminus E$. For that to work, $\gcd(n,10)=1$ is quite irrelevant.

In particular, as soon as $m$ is an integer such that $$ 1-\left(\frac{9}{10}\right)^m > 1-\frac{1}{n}, $$ there is a multiple of $n$ without digits $1$ in the interval $[1,10^m]$, so the least multiple of $n$ without digits $1$ in its decimal representation is always smaller than $n^{22}$. And in general $n^{22}$ is much smaller than $10^{\varphi(n)}$.

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