# Proof of the algorithm converting decimal into binary

I was trying to prove that every real fraction can be represented by the binary representation.

To be more specific, I want to show that, given any real fraction $$\frac{p}{q},\, p\in \mathbb{Z},q\in \mathbb{N}^+$$, there exists a series $$\sum_{I=-\infty}^\infty a_i2^{i}$$ s.t. $$\frac{p}{q}=\sum_{I=-\infty}^\infty a_i2^{i}$$, where $$a_i\in\{0,1\}.$$

The integral part is easy, by the successive divisions by $$2$$. We may obtain the decimal part by successive multiplications by $$2$$ (subtracting $$1$$ from the result of multiplication each time if necessary).

But I suddenly realize a problem, what if the decimal part is a repeating decimal, which means it doesn't end. Our step-by-step multiplication method is like an induction, which could not be applied to the infinite case.

Can someone else help me modify the proof? A lot of thanks!

• What happens in bases $10$ if the decimal part is repeating decimal that doesn't end? It's completely analogous. – fleablood Oct 19 '19 at 15:15
• Induction allows us to say something will "go on forever". It just doesn't allow us to say "the things that goes on forever is the same as the things that terminate". – fleablood Oct 19 '19 at 15:19
• Induction often does go on forever. In fact, it's rare when it doesn't. What you have is a statement "every $a_{k + jN} = d$" for every natural $N$". Nothing wrong with that. – fleablood Oct 19 '19 at 15:25

Assume that $$q$$ is odd. Then $$2\in\mathbb{Z}/(q\mathbb{Z})^*$$ and by Euler's theorem $$2^{\varphi(q)}\equiv 1\pmod{q},$$ so $$q$$ is a divisor of $$2^{\varphi(q)}-1$$ and $$\frac{1}{q} = \frac{0.11111111\ldots_2}{q}=0.\overline{B}$$ where $$B$$ is the binary string with $$\varphi(q)$$ bits representing $$\frac{2^{\varphi(q)}-1}{q}$$ in base $$2$$.
Once you have that the reciprocal of any odd natural number has a periodic base-$$2$$ representation you have very little to fill in.
• Hi Jack, can you explain a bit about why $\frac{1}{q}=0.\bar{B}$ where $B$ is the binary string with $\varphi(q)$ bits representing $\frac{2^{\varphi(q)}-1}{q}$ in base $2$? Thanks! – Sam Wong Oct 30 '19 at 2:23
• @SamWong: $0.\overline{1}_2=0.\overline{111\ldots 111}_2$ where the last period is made by $\varphi(q)$ bits. – Jack D'Aurizio Oct 30 '19 at 18:05