Is it possible to know what to multiply with a binary number so the answer contains a string of 1's?

Question

Is it possible to know what to multiply with a binary number so the answer contains a string of 1's (in binary)?

e.g. 17 * x = 10001 * x = 1111..... sol: 17 * 15 = 10001 * 1111 = 1111111

e.g. 11 * x = 1011 * x = 1111..... sol: 11 * 93 = 10001 * 1011101= 1111111111

is it possible to somehow know the value of x without checking every possible value?

edit: the initial no, which needs to be multiplied has will always be odd!

Answer 1

It is fairly easy to get a formula that works all the time, except that it may not always give you the smallest multiplier.

Let's say you have an odd number $y$. Then it is coprime with $2$, which, by Euler's theorem (https://en.wikipedia.org/wiki/Euler%27s_theorem) means that $y\mid 2^{\varphi(y)}-1$, where $\varphi$ is Euler's totient function ($\varphi(y)$ is the number of all numbers in the set $\{1, 2, \ldots, y-1\}$ coprime with $y$).

So, you can take $x=\frac{2^{\varphi(y)}-1}{y}$ and note that $2^{\varphi(y)}-1$ has all-ones in its binary representation.

As I said, this won't always give you the smallest number $x$. For example, $y=17$ gives you $\varphi(y)=16$ and so $x=\frac{2^{16}-1}{17}=3855$. For the other example you've given, $y=11$, $\varphi(y)=10$ and $x=\frac{2^{10}-1}{11}=93$.

Answer 2

So you are asking if for every $a$ there is a $b$ and $n$ such that:

$$a\cdot b = \underbrace{11...1}_n= {10^n-1\over 9}$$

So for each $a$ we are searching $n$ such that $9a|10^n-1$. We can do this by pigeonhole principle if $gcd(a,10)=1$:

Take a sequence $a_k = 10^k-1$ for $k\in \{1,2,3,...9a,9a+1\}$. Among them there are two that are having the same reminder modulo $9a$, so $$a_i\equiv a_j \pmod {9a}$$ We can assume $j>i$ so $$ 9a\mid (10^j-1)-(10^i-1) = 10^i(10^{j-i}-1)$$ Say $n=j-i$. Since $gcd(10,9a)=1$ we have by Euclid lemma: $$ 9a\mid 10^n-1$$ and we are done.

Answer 3

First way:

• This is possible if and only if $x$ is odd.
• Divide, using binary notation, $1/x$. You should get a periodic number. Let $p$ be the minimal period and $n$ its length.
• Write it in the language of series: $$\frac1x=p\sum_{k=1}^\infty\frac1{2^{nk}}=\frac p{2^n\left(1-\frac1{2^n}\right)}=\frac p{2^n-1}$$
• Now you have $$px=2^n-1$$

Second way:

If you know about Euler-Fermat's theorem (LFT is not enough), this solution is simpler:

If $x$ is odd, then $\gcd(x,2)=1$. Then $2^{\varphi(x)}\equiv 1\pmod x$. That is, $x$ divides $2^{\varphi(x)}-1$. (Note that $x$ could divide $2^t-1$ for smaller values of $t$). So you just compute $$\frac{2^{\varphi(x)}-1}x$$

Conclusion:

The fisrt method is slower but it yields the least possible solution, and the second one one can yield a much bigger solution, but it is much faster. The value of $n$ in the first period must divide $\varphi(x)$.