# For all $x\in\mathbb{N}^*$ there is some $y\in\mathbb{N}^*$ such that $xy$ contains only $0$s and $1$s.

The following is an interesting problem a friend of mine told me.

Let $\mathbb{N}^*=\mathbb{N}\setminus\{0\}$ and $U\subset \mathbb{N}^*$ be the set of positive integers whose base $10$ representation contains only $0$s and $1$s.

Show that for all $x\in\mathbb{N}^*$ there is some $y\in\mathbb{N}^*$ with $xy\in U$.

I have managed to solve it, but the solution is rather inelegant. Moreover, it uses Euler's theorem (on the totient function), and my friend implied that there should be a 'basic solution' -- that this problem should be solvable by an undergrad in an introductory course to real analysis.

I am interested to see what different solutions people can come up with. I can also post my own answer, but I figured I'd let you guys try your own hand at it before introducing some 'bias'.

• I do not know how to solve that, but do you know are there an infinite number of such y for every x? – user480281 Oct 15 '17 at 6:10
• @AntoinedePaladin Yes, there are. – Fimpellizieri Oct 15 '17 at 6:18
• OK, so we can assign to every $x_i$ an $\infty$-tuple $(y_{1i},y_{2i},...,y_{ki},...)$. If $x_i \neq x_j$ will then intersection of $(y_{1i},y_{2i},...,y_{ki},...)$ with $(y_{1j},y_{2j},...,y_{kj},...)$ when viewed as sets be a finite set always? – user480281 Oct 15 '17 at 6:24

Consider the following sequence

$$a_i = \sum_{j=0}^i 10^j=\overbrace{1\ldots1}^{i+1}$$

where $i$ takes value from $0$ to $x$.

That is $a_0=1, a_1=11$,$a_2=111$, and so on, where $a_x=\overbrace{1\ldots1}^{x+1}$.

By pigeonhole principle, when we take modulo $x$, two of them will share the same remainder, $r$. Let these two indices be $i$ and $j$, $t<s$, hence $a_t < a_s$.

$$a_t = xp + r$$

$$a_s=xq+r$$

$$a_s-a_t=x(q-p)$$

Notice that $a_s-a_t$ consists of only $0$ and $1$ and it is positive.

That is $a_s-a_t \in U$ and we can pick $y=q-p$.

• This fits very well my criteria of 'basic'. One of these situation where I'm left feeling stupid. Good job! – Fimpellizieri Oct 15 '17 at 6:21
• It can also be easily generalized, changing the $1$ in '$0$s and $1$s' to any other digit. Pretty awesome. – Fimpellizieri Oct 15 '17 at 6:23
• yup, or we can solve it for $1$ and $0$ and just multiply that number by the digit that you are interested. – Siong Thye Goh Oct 15 '17 at 6:28
• Yeah, after this comment, I'm pretty sure it's about time I went to bed. – Fimpellizieri Oct 15 '17 at 6:30

Well, since Siong very quickly provided an awesome answer, I will show my own (rather shameful) answer for those that are curious.

Fix $x \in\mathbb{N}^*$. Notice that we may assume without loss of generality that $(x,10)=1$.

Let $X=x\cdot\mathbb{N}^*$ and $U_0=U$. Observe that the problem is equivalent to showing that $X\cap U_0$ is nonempty.

Choose some $k_1,n_1\in\mathbb{N}$ with the property that $xn_1+k_1=u_0\in U_0$. It's easy to see that one can always pick $k_1<x$, although it's not necessary.
Now, let $U_1\subset\mathbb{N}^*$ be the set obtained by adjoining $k_1$ to the left of each $u\in U$, in base $10$ notation.
Suppose that $X\cap U_1$ is nonempty, so that for some $a\in\mathbb{N}$ one may write

$$x\cdot a=k_1\,\square$$

where $k_1\,\square$ is a number whose base $10$ representation has $k_1$ to the left, and $\square$ denotes the rest of its base $10$ representation, which consists solely of $0$s and $1$s.

If there are $d$ digits in $\square$, we may write $k_1\,\square=k_1\cdot 10^d+v$ for some $v<10^d$ in $U$. In this case:

\begin{align} x\cdot (a+n_1\cdot10^d) &=xa+xn_1\cdot10^d\\ &=\left(k_1\cdot10^d+v\right)+xn_1\cdot10^d\\ &=(xn_1+k_1)\cdot10^d+v\\ &=u_0\cdot10^d+v \end{align}

In other words, $x\cdot (a+n_1\cdot10^d) \in U_0$.
This means that the problem is equivalent to showing that $X\cap (U_0\cup U_1)$ is nonempty.

Now, suppose that we do not yet know whether $X\cap U_1$ is nonempty. We can repeat the process as follows.

Choose $k_2,n_2\in\mathbb{N}$ with the property that $xn_2+k_2=u_1\in U_1$ and let $U_2\subset\mathbb{N}^*$ be the set obtained by adjoining $k_2$ to the left of each $u\in U$, in base $10$ notation.
If $X\cap U_2$ is nonempty, one may write $x\cdot a =k_2\cdot 10^d+v$ for some $a,d\in\mathbb{N}$ and $v<10^d$ in $U$.

Proceeding as above, we will find that $x\cdot(a+n_2\cdot 10^d)=u_1\cdot10^d+v\in U_1$, which means that, like before, the problem is equivalent to showing that $X\cap(U_0\cup U_1 \cup U_2)$ is nonempty.

At this point, I believe the induction is clear.

Lemma: For each $j\geq1$, we may choose $k_j$ so that $k_j\equiv jk_1\pmod x$.

The lemma show that in at most $x$ steps we will have $u_{x-1}=xn_x+k_x\equiv 0\pmod x$, that is, $u_{x-1}\in X\cap U_{x-1}$, which completes the proof.

Proof of Lemma: Since $x$ and $10$ are coprime, by Euler's theorem we have that

$$10^{\varphi(x)}\equiv 1 \pmod x.$$

In particular, there are arbitrarily high powers of $10$ equivalent to $1$ modulo $x$.

We define the $k_j$ via induction. The base case $j=1$ is obvious, and remember it entails the existence of $n_1\in\mathbb{N}$ and $u_0\in U_0$ with $xn_1+k_1=u_0$.
For the inductive step, suppose $k_j$ has been defined so that $k_j\equiv jk_1\pmod x$. Choose some $d\in\mathbb{N}$ with $10^d\equiv 1 \pmod x$ and $u_0<10^d$. Then:

$$k_j\cdot 10^d+u_0=k_j\cdot 10^d+xn_1+k_1=xn_1+\left(k_j\cdot 10^d+k_1\right).$$

Notice that $\left(k_j\cdot 10^d+u_0\right)\in U_{j}$ and that $k_j\cdot 10^d+k_1\equiv k_j+k_1\equiv (j+1)k_1\pmod x$.
It follows that we may take $n_{j+1}=n_1$ and $k_{j+1}=k_j\cdot 10^d+k_1$. $\square$

This is only a part of the answer. Consider this as a hint.

Basically, after you choose $x$, what you have to do is, look at the decimal expansion of $\frac 1x$. Since ${x}$ is natural, ${\frac 1x}$ will be either a terminating or recurring decimal. If it is terminating, then $x$ must be a multiplication of powers of 2 and 5. Then you are done.

Now consider $x$ to be a prime other than 2, 3, 5. Then $\frac 1x$ will be a recurring decimal. For example take $x=7$. Then $$1/7=0.\bar{abcdefg} =\frac {abcdefg} {999999}$$ So $7×abcdefg=999999$.

$abcdefg$ is obviously divisible by 9. So just divide it by 9 to get suitable $y$.

For $x=3$, you have $y=37$ whose multiplication gives $111$.
I guess you can elaborate after this?

• This is an interesting approach. One of my other friends whom my first friend showed this problem to ran into some trouble with $x$'s containing factors of $3$.$${}$$ We may assume $x$ is coprime to $10$ $($and hence contains no factors of $2$ and $5)$. I must confess I'm not entirely sure how to proceed if, say, $x=3^a\cdot b$. That said, this method works beautifully whenever $x$ is coprime to $3$. – Fimpellizieri Oct 15 '17 at 6:48
• Well, simply by divisibility criterion of $3^a$, $1_{a}$ is a multiple. As for $3^a×b$, where $b$ is any number, you just have to put suitable number of $0's$ between the $1_{a}$ and multiply to suit your answer. – Abhishek Bakshi Oct 15 '17 at 6:57
• For example, let's say $x=63=3^2×7$. We have $3^2×p=111111111$ and $7×q=111111$. So just take $y=(10^6+1)pq$. You see what I did there? – Abhishek Bakshi Oct 15 '17 at 7:03
• What divisibility criterion for powers of $3$? – Fimpellizieri Oct 15 '17 at 7:15
• By the way, here we have $p=12345679$ and $q=15873$. This should give $y=195963158729962767$, but $63y=12345678999987654321$. While certainly it has an interesting structure, it does not solve our problem. – Fimpellizieri Oct 15 '17 at 7:57

Siong Thye Goh has a pretty cool solution but I have some kind of weird procedure that works too.

First, express $x=5^a\cdot2^b\cdot x'$. Since we can always multiply $x$ by $2^a\cdot 5^b$ to get $10^{a+b}x'$ and this is in $U$ precisely when $x'\in U$, we may assume that $\gcd(x,10)=1$ and just solve the problem.

Given $x\in \mathbb N^*$, are just looking for a positive integer $N=\sum_{i=0}^ka_i10^i$ with $a_i=0$ or $1$ such that $$\sum_{i=0}^ka_i10^i \equiv 0\pmod x.$$ (Once we find this, the $y$ in the problem will just be $N/x$.)

First write out the decimal expansion $x=\sum_{i=0}^d b_i10^i$ with $0\leq b_i\leq 9$. It is trivially true that $$\sum_{i=0}^d b_i10^i=x\equiv 0 \pmod x$$

Now we are going to find a number of the desired form (only has 0 and 1 in it's decimal expansion) congruent to this number.

Write each term $b_i 10^i$ as a sum of $b_i$ copies of $10^i$. Namely, $\overbrace{10^i+\cdots +10^i}^{b_i}$.

Since $(10,x)=1$, by Euler's theorem $(10^i)^{m\varphi(x)+1}=10^i$ for every non-negative integer $m$. Now we can replace all the $\sum_{i=0}^d b_i$ many powers of $10$ with distinct large powers of $10$. So when we take their sum, this will have only $0$s and $1$s in their decimal expansion because we are adding distinct powers of $10$.

The last two sentences also show that there are infinitely many "non boring" solutions, i.e. solutions that do not just differ from each other by multiplication by a power of $10$.

• This is a great, creative solution! You can assume $x$ is coprime to $10$ without loss of generality. First, write $x=x^*\cdot2^a5^b$ where $x^*$ contains no factors of $2$ or $5$. Then, solve the problem for $x^*$, obtaining $y^*$ with $x^*y^*=u\in U$. Finally, take $y=y^*\cdot2^b5^a$, so that $xy=x^*y^*\cdot 10^{a+b}=u\cdot10^{a+b}\in U$. – Fimpellizieri Oct 15 '17 at 7:04
• @Fimpellizieri Aha, I was just making that update. I couldn't sleep without fixing this. :D – Ravi Oct 15 '17 at 7:09
• =) Great job! ${}$ – Fimpellizieri Oct 15 '17 at 7:10

Here's a method which is similar to Siong Thye Goh's but for some $x$ yields a smaller result.

If $x=2^s5^t$, we may take $xy=10^{\max(s, t)}.$

Otherwise, let $b_i=10^i\bmod x$. By the pigeonhole principle there will be some $t$ and $s>t$ where $b_s=x-b_t$. One may then take $xy=10^s+10^t$.

For example if $x=7$, $(b_0,\dots)=(1, 3, 2, 6, 4, 5, 1,\dots)$ so we may take $t=0, s=3, xy=1001$.

• It is rather obvious that $7\cdot 1001$ does not result in a number that contains only $0$s and $1$s. – Fimpellizieri Oct 15 '17 at 20:14
• @Fimpellizieri OK, typo corrected. – Rosie F Oct 16 '17 at 5:27