An Introduction to Real Analysis
Section 1.2.4 notes
2025-11-30
The Section 1.2.3 notes for Katznelson and Katznelson (2024) used the division of \(23\) by \(5\) as an informal example when exploring Euclidean division. However, to this point only two concrete symbols have been introduced for integers: \(1\) for the distinguished element of the natural numbers and \(0\) for the additive identity of the integers. Apart from these two symbols, letters such as \(a\) or \(m\) have been used to refer to natural numbers or integers.
The goal of these notes is to introduce systems of concrete symbols for all the integers. These systems are called radix-\(b\) representations, where \(b\) is a natural number other than \(1\). Once radix-\(b\) representations have been introduced, expressions such as \(23\) and \(5\) will be properly defined and it will no longer be necessary to work informally with equations or inequalities such as \(23 \overset{!}{=}5 \cdot 4 + 3\) or \(2 \overset{!}{>}1\), respectively.
The development of radix-\(b\) representations for integers begins with their development for natural numbers. Once this has been established the extension to integers is straightforward.
Fix \(b \in \symbb{N}\setminus \{ 1 \}\). A radix-\(b\) representation of \(a \in \symbb{N}\) is a string of digits \(d_{j - 1} \dots d_1 d_0\) such that \[ a = \underbrace{d_{j - 1} b^{j - 1} + \dots + d_1 b^1 + d_0 b^0}_{\eqcolon d_{j - 1} \dots d_1 d_0} \] where \(j \in \symbb{N}\), \(1 \leq d_{j - 1} \leq b - 1\) and \(0 \leq d_k \leq b - 1\) for \(k \in \{ 0, \dots, (j - 1) - 1 \}\) if \(j \in \symbb{N}\setminus \{ 1 \}\). The \(j\) numbers \(d_0, d_1, \dots, d_{j - 1}\) are called the (radix-\(b\)) digits of \(a\). The highest-index digit \(d_{j - 1}\) is called the leading digit of \(a\). Informally, the non-leading digits are required to be between \(0\) and \(b - 1\) and the leading digit is required to be between \(1\) and \(b - 1\).
There are two results to establish for radix-\(b\) representations of natural numbers: Theorem 1 establishes that each \(a \in \symbb{N}\) has a radix-\(b\) representation and Theorem 2 establishes that the radix-\(b\) representation of \(a \in \symbb{N}\) is unique.
Theorem 1 Each \(a \in \symbb{N}\) has a radix-\(b\) representation.
Proof. By induction. The statement \(P(1)\) is true because \(1\) has the radix-\(b\) representation \(1\). Next assume that \(P(n)\) is true, so that \(n\) has the radix-\(b\) representation \(n = d_{j - 1} b^{j - 1} + \dots + d_1 b^1 + d_0 b^0\), whence \[\begin{equation} n + 1 = d_{j - 1} b^{j - 1} + \dots + d_1 b^1 + d_0 b^0 + 1 \label{eq:1} . \end{equation}\] Rewrite the right-hand side of \(\eqref{eq:1}\) according to the following procedure:
The pattern continues if necessary. The procedure either shows that \(P(n + 1)\) is true and terminates before reaching the final step, or the procedure reaches the final step, which begins “Otherwise \(d_{j - 1} = b - 1\), so \(d_{j - 1} + 1 = b\).” If this occurs, define \(d_{j - 1}' \coloneq 0\) and add \(d_{j - 1}' b^{j - 1}\) to the expression. Then define \(d_j' \coloneq 1\) and rewrite \((d_{j - 1} + 1) b^{j - 1}\) as \(d_j' b^j\). At this point the procedure has rewritten the right-hand side of \(\eqref{eq:1}\) as \(d_j' b^j + \dots + d_1' b^1 + d_0' b^0\), where \(d_j' = 1\) and \(d_0', d_1', \dots, d_{j - 1}' = 0\), so \(P(n + 1)\) is true. \(\blacksquare\)
Lemma 1 is necessary to justify part of the argument in the proof of Theorem 2.
Lemma 1 If \(a, b, c \in \symbb{N}\), \(a < b\) and \(c > 1\), then \(c^a \leq c^{b - 1}\).
Proof. Using the Section 1.1.3 notes for Katznelson and Katznelson (2024), \(a < b\) implies that \(a \leq b - 1\). There are thus two cases.
If \(a = b - 1\) then \(c^a = c^{b - 1}\) so \(c^a \leq c^{b - 1}\). If \(a < b - 1\) then there exists \(k \in \symbb{N}\) such that \(b - 1 = a + k\). A brief argument by induction shows that \(c^k > 1\). (Since \(c > 1\) by assumption, the statement \(P(1)\) is true. Next assume \(P(n)\) is true, so \(c^n > 1\). Then \(c^{n + 1} = cc^n > c\), and since \(c > 1\) it follows that \(c^{n + 1} > 1\), so \(P(n + 1)\) is true.) Using associativity of multiplication, \[\begin{align*} 1 &< c^k\\[0.75em] \implies c^a &< c^a c^k\\[0.75em] &= c^{a + k}\\[0.75em] &= c^{b - 1}, \end{align*}\] so \(c^a \leq c^{b - 1}\). \(\blacksquare\)
Theorem 2 The radix-\(b\) representation of \(a \in \symbb{N}\) is unique.
Proof. By contradiction, suppose \(a \in \symbb{N}\) has two radix-\(b\) representations \[\begin{align*} a &= d_{j - 1} b^{j - 1} + \dots + d_1 b^1 + d_0 b^0\\[0.75em] &= e_{k - 1} b^{k - 1} + \dots + e_1 b^1 + e_0 b^0. \end{align*}\] Call these the \(d\)- and \(e\)-representations of \(a\), respectively. The first task is to rule out the possibility that the \(d\)- and \(e\)-representations of \(a\) have different numbers of digits.
If \(j \neq k\), suppose without loss of generality that \(j < k\). Define \(D \coloneq \{ d_0, \dots, d_{j - 1} \}\) and \(J \coloneq \{ d_l \in D \colon d_l < b - 1 \} \subseteq D\). If \(J = \emptyset\) then \(d_0, \dots, d_{j - 1} = b - 1\). If not then by the definition of the linear order on \(\symbb{N}\) from Katznelson and Katznelson (2024, 2), for \(d_l \in J\) there exists \(m_l \in \symbb{N}\) such that \(d_l + m_l = b - 1\). Define \(L \coloneq \{ l \in \{ 0, \dots, j - 1 \} \colon d_l \in J \}\) and add \(\sum_{l \in L} m_l b^l + 1\) to the \(d\)-representation: \[\begin{align*} \MoveEqLeft[0] d_{j - 1} b^{j - 1} + \dots + d_1 b^1 + d_0 b^0\\[0.75em] &< d_{j - 1} b^{j - 1} + \dots + d_1 b^1 + d_0 b^0 + \sum_{l \in L} m_l b^l + 1\\[0.75em] &= (b - 1)b^{j - 1} + \dots + (b - 1)b^1 + (b - 1)b^0 + 1\\[0.75em] &= b^j. \end{align*}\] By Lemma 1 \(b^j \leq b^{k - 1}\). Thus by transitivity, \[\begin{align*} a &= d_{j - 1} b^{j - 1} + \dots + d_1 b^1 + d_0 b^0\\[0.75em] &< b^j\\[0.75em] &\leq b^{k - 1}\\[0.75em] &\leq e_{k - 1} b^{k - 1} + \dots + e_1 b^1 + e_0 b^0\\[0.75em] &= a, \end{align*}\] which is a contradiction. Hence \(j = k\), so the \(d\)- and \(e\)-representations of \(a\) have the same number of digits.
If \(j = k = 1\) then \(a = d_0 b^0 = e_0 b^0\), so \(d_0 = e_0\) and the representations are identical.
If \(j = k = 1 + 1\) then \(a = d_1 b + d_0 = e_1 b + e_0\). In this case the \(d\)- and \(e\)-representations of \(a\) are each in the form \(a = qb + r\) with \(q \in \symbb{Z}\) and \(0 \leq r \leq b - 1\). By Euclidean division as in the Section 1.2.3 notes for Katznelson and Katznelson (2024), \(q\) and \(r\) are unique, whence \(d_1 = e_1\) and \(d_0 = e_0\) and the representations are identical.
The case when \(j = k > 1 + 1\) proceeds by repeated application of Euclidean division. By rewriting both representations \[\begin{align*} a &= (d_{j - 1} b^{(j - 1) - 1} + \dots + d_1) b + d_0\\[0.75em] &= (e_{k - 1} b^{(k - 1) - 1} + \dots + e_1) b + e_0. \end{align*}\] Again the \(d\)- and \(e\)-representations of \(a\) are each in the form \(a = qb + r\) with \(q \in \symbb{Z}\) and \(0 \leq r \leq b - 1\). Again by Euclidean division \(q\) and \(r\) are unique whence \(d_{j - 1} b^{(j - 1) - 1} + \dots + d_1 = e_{k - 1} b^{(k - 1) - 1} + \dots + e_1\) and \(d_0 = b_0\). This proves that the first digit in each representation is identical.
To see that the second digit in each representation is identical, define \(a_1 \coloneq d_{j - 1} b^{(j - 1) - 1} + \dots + d_1 = e_{k - 1} b^{(k - 1) - 1} + \dots + e_1\), so that these are two representations of \(a_1\). If there are only two summands in each representation of \(a_1\), then again by Euclidean division \(d_{1 + 1} = e_{1 + 1}\) and \(d_1 = e_1\), so the representations are identical. If there are more than two summands in each representation of \(a_1\), then factor out \(b\) from all summands but the last as before. By Euclidean division this proves that \(d_1 = e_1\), so the second digit in each representation is identical.
The repeated application of Euclidean division eventually terminates since the \(d\)- and \(e\)-representations are of finite length. This method shows that \(d_0 = e_0\), \(d_1 = e_1\), and so on, until \(d_{j - 1} = e_{j - 1}\) and the two representations have been proven identical. \(\blacksquare\)
Again fix \(b \in \symbb{N}\setminus \{ 1 \}\). Extending radix-\(b\) representations from natural numbers to integers requires a minor extension to the definition of radix-\(b\) representations to handle integers \(m \in \symbb{Z}\setminus \symbb{N}\).
The radix-\(b\) representation of \(0\) is defined to be \(0\).1 This is mostly consistent with the definition of radix-\(b\) representations of natural numbers because the number of digits in the representation of \(0\) is \(1\), so \(j = 1\) and \(d_0 = 0\). It is not fully consistent, however, because the leading digit is \(0\).
If \(m \in \{ -a \colon a \in \symbb{N}\}\) then by definition \(m = -a\) where \(a \in \symbb{N}\). By Theorem 1 and Theorem 2 \(a\) has the unique radix-\(b\) representation \(a = d_{j - 1} \dots d_1 d_0\). The radix-\(b\) representation of \(-a\), and hence \(m\), is defined to be \(-d_{j - 1} \dots d_1 d_0\).
With the foregoing definitions, Theorem 1 and Theorem 2 can be extended to analogous theoremata in Theorem 3 and Theorem 4, respectively.
Theorem 3 Each \(m \in \symbb{Z}\) has a radix-\(b\) representation.
Proof. Consider \(m \in \symbb{Z}\). Because of the partition \(\symbb{Z}= \symbb{N}\uplus \{ 0 \} \uplus \{ -a \colon a \in \symbb{N}\}\), there are three possibilities. If \(m \in \symbb{N}\), then by Theorem 1 \(m\) has a radix-\(b\) representation \(m = d_{j - 1} \dots d_1 d_0\). If \(m = 0\) then the radix-\(b\) representation of \(m\) is defined to be \(0\). If \(m \in \{ -a \colon a \in \symbb{N}\}\) then \(a\) has the radix-\(b\) representation \(d_{j - 1} \dots d_1 d_0\), so \(-a\) and hence \(m\) has the radix-\(b\) representation \(-d_{j - 1} \dots d_1 d_0\). \(\blacksquare\)
Theorem 4 The radix-\(b\) representation of \(m \in \symbb{Z}\) is unique.
Proof. Consider \(m \in \symbb{Z}\). Because of the partition \(\symbb{Z}= \symbb{N}\uplus \{ 0 \} \uplus \{ -a \colon a \in \symbb{N}\}\), there are three possibilities. If \(m \in \symbb{N}\) then by Theorem 2 \(m\) has a unique radix-\(b\) representation. If \(m = 0\) then \(0\) is the only radix-\(b\) representation that has been defined for \(m\), so the representation is unique. If \(m \in \{ -a \colon a \in \symbb{N}\}\) had two distinct radix-\(b\) representations \(-d_{j - 1} \dots d_1 d_0\) and \(-e_{k - 1} \dots e_1 e_0\) then \(-m = -(-a) = a \in \symbb{N}\) would have two distinct radix-\(b\) representations \(d_{j - 1} \dots d_1 d_0\) and \(e_{k - 1} \dots e_1 e_0\), which is a contradiction. \(\blacksquare\)
Without a good system of representations, integers are difficult to use in practice. For example, writing integers as \(\dots, -1 - 1 - 1, -1 - 1, -1, 0, 1, 1 + 1, 1 + 1 + 1, \dots\) is impractical for all but trivial record-keeping and calculations. Historically a number of numeral systems have been developed, such as the Babylonian and Roman numeral systems, both of which predate the development of radix-\(b\) representations. However, radix-\(b\) representations are probably the best numeral system devised to date for arithmetic, hence their ubiquity.
Radix-\(b\) representations are so ubiquitous, particularly in their base-ten form, that they may be confused with integers themselves. However, they are only an effective system of representations of integers—they are not the integers themselves. It is rarely necessary to use systems other than radix-\(b\) representations, but when studying computer science and engineering it is frequently necessary to change radices, for example from base-ten to base-two or vice-versa. For example, both Patt and Patel (2020) and Harris and Harris (2022) discuss conversions between base-ten and base-two. The need to change representations of an integer \(m \in \symbb{Z}\) from radix-\(b\) to radix-\(\beta\) makes clear that \(m\) exists independently of the system chosen for its representation.
In order to use a radix-\(b\) representation it’s necessary to have \(b\) ordered symbols to use as digits. These symbols represent the the first \(b\) non-negative integers. For example, the ten Arabic numerals \(0, 1, 2, 3, 4, 5, 6, 7, 8, 9\) are standard for radix-ten representations. With this choice of symbols, the non-negative integers begin \(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, \dots\). For radix-sixteen representations it would be necessary to have sixteen symbols. This is commonly accomplished by appending the symbols \(\symsfup{A}\), \(\symsfup{B}\), \(\symsfup{C}\), \(\symsfup{D}\), \(\symsfup{E}\), \(\symsfup{F}\) in order to the Arabic numerals, so that symbols used for radix-sixteen representations are \(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, \symsfup{A}, \symsfup{B}, \symsfup{C}, \symsfup{D}, \symsfup{E}, \symsfup{F}\).
It would also be legitimate to forego the Arabic numerals and use a completely different set of symbols. The preceding theoremata apply irrespective of the symbols used. If the symbols \(0, 1, 2, 3\) are used for radix-four representations, the natural numbers will be written as \(1, 2, 3, 10, \dots\) . On the other hand, if the symbols \(\heartsuit, \clubsuit, \diamondsuit, \spadesuit\) are used instead, the natural numbers will be written as \(\clubsuit, \diamondsuit, \spadesuit, \clubsuit \heartsuit, \dots\) . The Arabic numerals are more familiar but they have no inherent mathematical properties.
After choosing a set of symbols another issue is changing radices: computing the radix-\(b\) representation of \(a \in \symbb{N}\) given its radix-\(\beta\) representation. Suppose there were an algorithm that could take as input the radix-\(\beta\) representation of \(a\) and compute \(q_0\) and \(r_0\) in the equation \(a = q_0b + r_0\) according to Euclidean division; such an algorithm is called a division algorithm. If \(q_0 = 0\), or whatever is the equivalent of \(0\) in the system of symbols being used, then \(a = r_0\) is the unique radix-\(b\) representation of \(a\). If \(q_0 \neq 0\) then the radix-\(b\) representation of \(a\) must have two or more digits, so \(b\) can be factored out of all summands except the first.2 Equate this with the representation of \(a\) obtained from the division algorithm: \[\begin{align*} a &= d_{j - 1} b^{j - 1} + \dots + d_1 b^1 + d_0 b^0\\[0.75em] &= (d_{j - 1}b^{(j - 1) - 1} + \dots + d_1)b + d_0\\[0.75em] &= q_0b + r_0. \end{align*}\] By Euclidean division \(d_{j - 1}b^{(j - 1) - 1} + \dots + d_1 = q_0\) and \(d_0 = r_0\), so the first digit in the radix-\(b\) representation of \(a\) is the remainder obtained from the division algorithm. If \(1 \leq q_0 \leq b - 1\) then \(q_0\) is the second digit.
If \(q_0 \geq b\) there are least three digits, and the remainder returned by the division algorithm when applied to \(q_0\) will be \(d_1\), the second digit in the radix-\(b\) representation of \(a\). In this way, repeatedly applying the division algorithm to prior quotients until the quotient returned is zero will compute the radix-\(b\) representation of \(a\).
The Python code below applies Python’s built-in division algorithm to compute the radix-\(b_2\) representation of \(a \in \symbb{N}\) given its radix-\(b_1\) representation. The code permits \(b_1\) and \(b_2\) between two and thirty-six, inclusive, which is a convenient range of radices made possible by using the ten Arabic numerals and twenty-six Latin letters as symbols for digits. The code defines a function change_base() that takes \(a\), \(b_1\) and \(b_2\) and uses a number of auxiliary function to change radices from \(b_1\) to \(b_2\). Because the Python interpreter assumes numbers are in their radix-ten representation, change_base() calls base_ten() to convert \(a\) from its radix-\(b_1\) representation to its radix-ten representation before passing the result to a_in_base_b(), which computes the radix-\(b_2\) representation of \(a\). The function a_in_base_b() is the heart of the program, because it repeatedly applies a division algorithm to succeeding quotients to compute the digits in the radix-\(b_2\) representation of \(a\). However, a number of additional details have to be taken care of in order to create a functioning program.
import numpy as np
import string
# Define list of letters ['A', 'B', ..., 'Z']
# and numbers [0, 1, ..., 9],
# and concatenate them
letters = list(string.ascii_uppercase)
numbers = list(range(9 + 1))
digits = numbers + letters
# Define several auxiliary functions below
# Given a list of digits,
# return their base-10 representations
# For example, [1, 2, 'F']
# returns [1, 2, 15]
def base_ten_symbols(s):
index = digits.index(s)
return(index)
# Python's remainder operator %
# will return the remainder in its base-ten
# form, # so it's necessary to rewrite the
# remainder using the appropriate symbol
# For example, 13 returns 'D'
def letter_remainders(r):
digit = digits[r]
return(digit)
# Compute the base-ten representation of a,
# given its base-b representation
def base_ten(a, b):
# Get the base-ten symbols for each of the
# digits of a
# For example, ['F', 'Z', 3] should return
# [15, 35, 3]
a = np.array(list(map(base_ten_symbols, a)))
# Lay out the exponents
# For example, if b is 4 and a has 3 digits,
# then exponents should be [2, 1, 0]
num_digits = len(a)
exponents = np.flip(np.arange(num_digits))
# powers_of_b would then be [4^2, 4^1, 4^0]
powers_of_b = b ** exponents
# The base-ten representation of a is then
# just the dot product of a and powers_of_b
base_ten = np.dot(a, powers_of_b)
return base_ten
# Compute the base-b representation of a
# where a is base-ten
def a_in_base_b(a, b):
# Set up list to hold the digits
digits = []
# By Euclidean division, a = qb + r
# Apply Python's division algorithm to
# compute q and r;
# Because the remainder will be returned in
# base-ten form, it needs to be passed
# through letter_remainders() to get the
# appropriate digit symbol
# For example, if a % b returns 13
# then letter_remainders converts that to D
q = a // b
r = letter_remainders(a % b)
# Add r to the list of digits
digits.insert(0, r)
# As long as the prior q is not zero, apply
# the division algorithm to q. This produces
# a new q and r with respect to the prior q.
# The r is the next digit in the base-b
# representation of a. The new q is used to
# check if another application of the
# division algorithm is necessary, and
# the division algorithm is applied
# to the new q if so.
while q != 0:
r = letter_remainders(q % b)
digits.insert(0, r)
q = q // b
# Return the array of digits
return np.array(digits)
# Compute the base-b2 representation of a
# given its base-b1 representation
# Note that b1 and b2 are assumed to be in
# base-ten format
def change_base(a, b1, b2):
# Compute the base-ten values of the digits
# of a;
# If any of them are b1 or higher,
# then throw an error
# For example, 51 is not a valid base-3
# number
a_b10 = list(map(base_ten_symbols, a))
a_b10 = np.array(a_b10)
any_digits_too_big = np.any(a_b10 >= b1)
if any_digits_too_big:
msg = f"""{a} is an invalid representation
of a base-{b1} natural number."""
raise Exception(msg)
# Otherwise, get the base-ten representation
# of a, and then let a_in_base_b() compute
# the base-b2 representation of the result
a = base_ten(a=a, b=b1)
return(a_in_base_b(a=a, b=b2))
# A bunch of tests
test1 = np.array([1, 0, 1, 1])
return1 = change_base(test1, 2, 10)
expect1 = np.array([1, 1])
result1 = np.array_equal(return1, expect1)
print(f'Test 1 pass? {result1}')
test2 = np.array([8])
return2 = change_base(test2, 10, 10)
expect2 = np.array([8])
result2 = np.array_equal(return2, expect2)
print(f'Test 2 pass? {result2}')
test3 = np.array([1, 5])
return3 = change_base(test3, 10, 16)
expect3 = np.array(['F'])
result3 = np.array_equal(return3, expect3)
print(f'Test 3 pass? {result3}')
test4 = np.array(['F', 2],
dtype=object)
return4 = change_base(test4, 16, 10)
expect4 = np.array([2, 4, 2])
result4 = np.array_equal(return4, expect4)
print(f'Test 4 pass? {result4}')
test5 = np.array(['F', 2],
dtype=object)
return5 = change_base(test5, 16, 2)
expect5 = np.array([1, 1, 1, 1, 0, 0, 1, 0])
result5 = np.array_equal(return5, expect5)
print(f'Test 5 pass? {result5}')
test6 = np.array(['C', 9, 'A'],
dtype=object)
return6 = change_base(test6, 16, 19)
expect6 = np.array(['8', 'H', 'F'])
result6 = np.array_equal(return6, expect6)
print(f'Test 6 pass? {result6}')
test7 = np.array(['Z', 1, 3, 'F', 8],
dtype=object)
return7 = change_base(test7, 36, 22)
expect7 = np.array(['B', '9', '3', 'F',
'8', 'G'])
result7 = np.array_equal(return7, expect7)
print(f'Test 7 pass? {result7}')
test8 = np.array(['Z', 1, 3, 'F', 8],
dtype=object)
return8 = change_base(test8, 36, 3)
expect8 = np.array([1, 1, 0, 0,
2, 2, 0, 1,
0, 2, 1, 0,
0, 2, 0, 2, 2])
result8 = np.array_equal(return8, expect8)
print(f'Test 8 pass? {result8}')
# This call to change_base() throws an error,
# since 93 is not a valid base-7 number
test9 = np.array([9, 3])
# return9 = change_base(test9, 7, 3)Hence the radix-\(b\) representation of \(0\) is independent of the choice of \(b\). (The radix-\(b\) representation of \(1\) is also independent of the choice of \(b\).)↩︎
If the radix-\(b\) representation of \(a\) had only one digit then \(a = d_0\) and by definition, \(1 \leq a \leq b - 1\) since \(0\) is not a natural number. This is a contradiction because \(q_0\) and \(r_0\) in the equation \(a = q_0b + r\) must be unique, so it’s not possible to write \(a = q_1b + d_0\) with \(q_1 = 0\).↩︎