0
$\begingroup$

Prove that for any given positive integer $n$,there exists a number having digits $0,1$ which is divisible by $n$.

Let that number be of the general form: $x=\overline {b_kb_{k-1}...b_1b_0}$ where $b_i\in \{0,1\}$.How can we construct $x$ to be divisible by the given $n$?

$\endgroup$
2

2 Answers 2

3
$\begingroup$

Let $$a_k = \underbrace{111...11}_{k} = {10^k-1\over 9}$$

So, among $a_1,a_2,...a_{n+1}$ two must have the same remainder modulo $n$, say $a_i$ and $a_j$ and $i>j$. Thus $$n\mid a_i-a_j ={10^i-10^j\over 9} =10^j{10^{i-j}-1\over 9}= \underbrace{111...11}_{i-j}\underbrace{000...00}_{j}$$

$\endgroup$
0
2
$\begingroup$

Note that $10^{k \, \varphi(n)} \equiv 1,$ where $\varphi$ is the Euler phi function and $k\in \mathbb{N}$, and then see that $$ \sum_{k=1}^n 10^{k \, \varphi(n)} \equiv 0 \pmod n $$ Thus the integer whose decimal expansion has a 1 at positions $k \, \varphi(n)$ for $k=1,\dots,n$ and zeros everywhere else is divisible by $n.$

Alas, this only works if $n$ is relative prime to 10, and needs to be modified otherwise.

$\endgroup$
2
  • $\begingroup$ $10^\varphi (n)\equiv 1\pmod n $ if $n$ is prime with 10. $\endgroup$ Dec 1, 2017 at 21:20
  • $\begingroup$ Good point, thanks $\endgroup$ Dec 1, 2017 at 21:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .