Why are every number (integer) exactly divisible by 5 in decimal number system but not in binary number system?

Question

I have wondered during the number system classes in computer science that

if 1/5 in decimal number system results in 0.2

why 1/101 in binary number system (where, 0b1 = 1, 0b101 = 5) results in 0.00110011... ?

Answer 1

You can represent any number in base ten in the following fashion:

$$ N = a_0 \times 10^0 + a_1 \times 10^1 + … + a_m \times 10^M. $$

Ignoring the decimal part. Now, what happens if you divide that by a number of the form $B = 2^k 5^l$? Well, simple enough, each of the powers of $10$ is divided by the number $B$, resulting in something of the new form:

$$ \frac{N}{B} = a_0 \times \frac{10^0}{B} + a_1 \times \frac{10^1}{B} + … + a_m \times \frac{10^M}{B} = \\ a_0 \times (2^{0-k} 5^{0-l}) + a_1 \times (2^{1-k} 5^{1-l}) + … + a_m \times (2^{M-k} 5^{M-l}). $$

Next, we think of a decimal number with a finite number of decimal places as a number which may be multiplied by a number $10^P$, for a $P=\text{number of decimal places}$ in such a way that there are no factors to the power $-1$.

Lets multiply our previous number by $10^P$:

$$ \left( \frac{N}{B} \right) 10^P = a_0 \times (2^{P+0-k} 5^{P+0-l}) + a_1 \times (2^{P+1-k} 5^{P+1-l}) + … + a_m \times (2^{P+M-k} 5^{P+M-l}). $$

Fair enough, we get exponents for our $2$ and $5$ which are larger than zero. But what happens if we divide the number by a number $p \neq {5,2}$? No matter how big $10^P$ is, the new number $\left( \frac{N}{B\ \times\ p} \right) 10^P$ will have $p^{-1}$ all throughout the number, unless all of the $a_i$ are multiples of $p$, of course. That means that no matter how large $P$ from $10^P$ is, we will never be able to eliminate $p^{-1}$! Therefore we get a non-finite amount of decimal places.

Maybe this is a bit more elaborate, but I like to think of it this way to get why decimal point places are finite or infinite.

Answer 2

Let's do the necessary division the long way:

$$\frac 15 = 0.2_{10}=0.00110011\dots_{2}$$

where we use $X_n$ to refer to the number $X$ in base $n$. For the base-$10$ representation, we have a fraction of $1$ and so we must start on the RHS of the decimal point, where we first have the tenths-place, followed by the hundredths-place, and so on. We need to know how many tenths will represent $\frac 15$, so we do this division:

$${\frac 15\over \frac 1{10}}=\frac {10}1\cdot \frac 15=2$$

Having $2$ tenths and no remainder, we make the representation $0.2_{10}$. Notice that $5$ divides $10$ evenly, causing our division to have no remainder. In the case of binary, we do the following, noting that we have $\frac 15\lt \frac 14\lt\frac 12$ which causes our first two digits to be $0$:

$$\frac 15\gt \frac 18 \to {\frac 15\over \frac 18}=\frac 81\cdot \frac 15=1\frac35$$

Here we have $1$ eighth, and also $\frac 35$ eighths remaining, and so we must also do the following:

$$\frac 3{40}\gt \frac 1{16}\to {\frac 3{40}\over\frac 1{16}}=\frac {16}{1}\cdot \frac 3{40}=1\frac 15$$

Again we end up with $1$ sixteenth, as well as $\frac 15$ sixteenths, and the process starts again at the beginning, except now we are working with $\frac 15\cdot\frac 1{16}$ instead of our original $\frac 15$. In binary, the $\frac 1{16}$ portion simply shifts our results to the right by $4$ digits, and we can see how we would repeat this pattern indefinitely: $0.00110011\dots_2$. In particular, it should be clear that if the denominator of a fraction has at least one factor not in common with the base in which the number is to be represented, the fractional part will be infinite and repeating using placeholder notation.

Answer 3

In general, a rational number $m/n$ (we assume here and for the rest of this answer that $m$ and $m$ are whole numbers with no common factors, so that this is written in lowest terms; for simplicity, we will also assume that $m < n$) will have a terminating expansion when written in base $B$ if and only if the denominator $n$ has among its prime factors only numbers that are also factors of $B$.

Here's why. Suppose in some number base we can write $$ m/n = (0.a_1 a_2 a_3 \dots a_k)_B$$ where each of the $a_i$ is a digit in the number base, and the subscript $B$ at the end just lets us know which base we are writing the number in.

If so, then that means $$\frac{m}{n} = \frac{(a_1 a_2 .... a_k)}{B^k}$$ where $(a_1 a_2 \dots a_k)$ denotes the string of digits, interpreted as a whole number (in particular, it does not mean the product of the $a_i$s).

Now the fraction on the right-hand side of the above equality might not be in lowest terms. For example, in Base 10 we have $3/4 = 0.75$, which we can write as $$\frac{3}{4} = \frac{75}{10^2}$$ The numerator($75$) and the denominator ($10^2 = 100$) both contain factors of $5^2$, which can be taken out. But when we are done, whatever prime factors that are left in the denominator will be factors that are leftover from canceling some of the factors of $10^k$. Since the only prime factors of $10$ are $2$ and $5$, whatever is left in the denominator after canceling will be some product of $2$s and $5$s.

The converse of this is true, too: If you have a fraction whose denominator only contains $2$s and $5$s, you can multiply both numerator and denominator by some more $2$s and $5$s until you have an equivalent fraction that looks like $\frac{ \text{some number}}{10^k}$ and then it is clear how to write it as a terminating decimal.

So it is in other bases. If you write fractions in "heximel" (Base 6) then a fraction will terminate only if its denominator contains some combinations of $2$s and $3$s (and nothing else). For example, we have $$\frac{1}{3} = (0.2)_6$$ $$\frac{1}{2} = (0.3)_6$$ $$\frac{1}{4} = (0.13)_6$$ $$\frac{1}{9} = (0.04)_6$$ $$\frac{1}{12} = (0.03)_6$$ but $$\frac{1}{5} = (0.1111 \dots)_6$$