ON BITS AND RATIONAL NUMBERS

We, human beings, have ten fingers. This might be the reason why we are used to count by ten digits or decimal digits. 

Computers are designed to count in twos only; 0 and 1. These are called as binary digits or bits. 

A sequence of bits is a binary expansion of a number. For example, the sequence 110 is the binary expansion of the number 6. This is determined by computing  (1 x 4) + (1 x 2) + 0.

Hence, a binary sequence of the form 

is equivalent to the number computed in 

This binary expansion is unique to every number and every number has a unique binary expansion.

A rational number of the form s/t where s and t integers, t greater than 0 can be represented by a binary expansion. For example, the rational number 1/4 is represented uniquely by 0.01 and the rational number 11/4 is represented uniquely by 10.11 since 19/8 = 1 x 2 + 0 + (0 x 1/2) +  (1 x 1/4) + (1 x 1/8). 

The sequence 10 in 10.011 is called the whole part and the sequence 011 after the binary point is called the fractional part of the binary expansion.

Computers are designed so that it can store a binary sequence of a finite length in its memory. 

For example, if the computer is designed to store 12 bits of the fractional part only, then the rational 1/5 or 0.2  will be stored as 0.001100110011.This is only equivalent to 0.19970703125 and not 0.2. Therefore, the 12-bit computer can not store the binary expansion of 1/5 completely. 

Note that the fractional part of the binary expansion is periodic with period 0011 of length 4. Hence, an exact binary expansion for 1/5 is 0.(0011) where the sequence inside the parenthesis is a periodic sequence.

Note that the number 5 and 2 are relatively prime, that is, their greatest common divisor is equal to 1. 

Thus, a  fractional part of the binary expansion has a period if the denominator of the rational number has a factor which is relatively prime to 2.

If two numbers x and y are relatively prime, then we can find the smallest positive integer m such that the number 

is divisible by y.

This smallest positive integer m is called the multiplicative order of x under modulo y.

The multiplicative order of 2 under modulo 5 is 4, since 4 is the smallest positive integer such that 2^4 -1 = 15 is divisible by 5. 

We can obtain 15 from 5 by multiplying 5 by 3.

Thus, we have

The binary expansion of 3 is equal to 11. Since 4 is the multiplicative order of 2 under modulo 5, we can write the binary expansion of 3 as 0011 instead of 11. 

Therefore, 

by Felix P. Muga II
Associate Professor, Mathematics Department, Ateneo de Manila University
Senior Fellow, Center for People Empowerment in Governance

The Mathematics of Kits (specifically Bits)