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
$\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$
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$
  • $\begingroup$ $10^\varphi (n)\equiv 1\pmod n $ if $n$ is prime with 10. $\endgroup$ – Fabio Lucchini Dec 1 '17 at 21:20
  • $\begingroup$ Good point, thanks $\endgroup$ – Reiner Martin Dec 1 '17 at 21:21

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.