Representation of numbers in arbitrary bases

When we write a number in base 10, a_na_n−1a_n−2⋅⋅⋅a₁a₀, it must be intended as

a_n 10ⁿ + a_n−110ⁿ⁻¹ + ... + a₁ 10 + a₀

where a_i are integers such that 0 ≤ a_i < 10. For example 2452 is

2452 = 2⋅ 10³ + 4 ⋅ 10² + 5 ⋅ 10 + 2

where the a_i are such that 0 ≤ a_i < 8.

We can obtain the digits of a number in the following way: if we divide a number by 10 its remainder will be its last digits.

2452 = 245 ⋅ 10 + 2

If we continue and divide the quotient and take the remainder of the division, we find the next digit

245 = 24 ⋅ 10 + 5

Thus the coefficients a_i of the decimal representation of a number a univocally determined. The role played by the base 10 can be played out by any other integer ≥ 2. For example is the base is 8

a_na_n−1a_n−2⋅⋅⋅a₁a₀ = a_n 8ⁿ + a_n−18ⁿ⁻¹ + ... + a₁ 8 + a₀

In general the following proposition holds true

Proposition 4.36. Let b ≥ 2 an integer. Any integer a ≥ 0 can be represented univocally using b as a base as

a = r_n bⁿ + r_n−1bⁿ⁻¹ + ... + r₁ b + r₀

with the r_i such that 0 ≤ a_i < b.

Proof. We use induction. If a = 0 there's nothing to prove. Supposing the proposition true for any integer <a we prove it for a. Dividing a by the b base we have

a = b ⋅ q + r₀ 0 ≤ r₀ < b

The quotient q is less than a thus for the induction hyphotesis is representable univocally as

q = r_n bⁿ⁻¹ + r_n−1 bⁿ⁻² + ... + r₂ b + r₁

since the r_i are univocally determined and such that 0 ≤ r_i < b ∀i, it follows that

a = b ⋅ q + r₀ = b(r_n bⁿ⁻¹ + r_n−1 bⁿ⁻² + ... + r₂ b + r₁) + r₀

This expression is unique since both quotient q and remainder r₀ of the first division are univocally determined; the expression of q is unique for the induction hyphothesis.□

Any number less than b is represented by a unique "symbol" or digit, there are exaclty b such digits. In the binary system b = 2 there are two digits 0 and 1.

« Euler's function and theorem Index Complex Numbers »