An Introduction to Real Analysis
Section 1.2.3 notes
2025-11-23
The goal of these notes is to prove that given \(m \in \symbb{Z}\) and \(n \in \symbb{Z}\setminus \{ 0 \}\), there exist unique \(q, r \in \symbb{Z}\) such that \(m = nq + r\) and \(0 \leq r \leq \lvert n \rvert - 1\). Given \(m\) and \(n\), any method of computing \(q\) and \(r\) is called dividing \(m\) by \(n\). The topic in general is called Euclidean division, or division with remainder. Informally, if there are \(m\) units of some quantity then \(q\) represents the number of times that \(n\) units can be taken from \(m\), and \(r\) represents what, if anything, can be taken from \(m\) once \(m\) has fewer than \(n\) units remaining. For example, if \(m \overset{!}{=}23\) and \(n \overset{!}{=}5\), then dividing \(23\) by \(5\) results in the equation \(23 \overset{!}{=}5 \cdot 4 + 3\). Therefore \(5\) can be taken from \(23\) \(4\) times and then \(3\) units can be taken.
Slightly more abstractly, the quotient \(q\) represents the number of multiples of \(n\) that is as close as possible to \(m\) while being less than \(m\), and the remainder \(r\) is the addition to \(nq\) needed to create equality with \(m\). This second perspective allows the division of \(m\) by \(n\) to be generalized from \(m, n \in \symbb{N}\) to almost arbitrary integers, as long as \(n \neq 0\).1 Because there is always a multiple of \(n\) within \(\lvert n \rvert - 1\) units of \(m\), the remainder \(r\) is always between \(0\) and \(\lvert n \rvert - 1\).
Euclidean division is not covered by Katznelson and Katznelson (2024), but it is a fundamental result pertaining to the integers that should be included in the development of the number systems. For example, Euclidean division is important in the following applications:
Theorem 1 proves Euclidean division. However, proving that \(q\) and \(r\) exist and are unique is not the same as computing \(q\) and \(r\), so after proving Theorem 1 an explicit method of dividing \(m\) by \(n\) will be given. The method is derived from the informal work that leads to the proof of Theorem 1.
Before proceeding to Euclidean division it will be helpful to extend the well-ordering principle from \(\symbb{N}\) to \(\symbb{N}\uplus \{ 0 \}\).
Lemma 1 If \(M \subseteq \symbb{N}\uplus \{ 0 \}\) is not empty, then \(M\) has a least element.
Proof. If \(0 \notin M\) then \(M \subseteq \symbb{N}\), so \(M\) has a least element by the well-ordering principle. If \(0 \in M\) then it was proven in the Section 1.2.2 notes for Katznelson and Katznelson (2024) that \(m \in \symbb{N}\) if and only if \(m > 0\). If \(m \in M\) and \(m \neq 0\), then \(m \in \symbb{N}\) so \(0 < m\). It follows that for all \(m \in M\), \(0 \leq m\), so \(0\) is the least element of \(M\). \(\blacksquare\)
Lemma 2 For all \(m, n, o, p \in \symbb{Z}\), if \(m < n\) and \(o \leq p\), then \(m + o < n + p\).
Proof. If \(o = p\) then using Exercise 1.2.1 from Katznelson and Katznelson (2024), \(m < n\) implies that \(m + p < n + p\), which implies that \(m + o < n + p\). If \(o < p\) then by definition \(p - o \in \symbb{N}\), and \(n - m \in \symbb{N}\) as well. Using Lemma 1 from the same exercise, \[\begin{align*} (n - m) + (p - o) &= (n + (-m)) + (p + (-o))\\[0.75em] &= (n + p) + ((-m) + (-o))\\[0.75em] &= (n + p) - (m + o)\\[0.75em] &\in \symbb{N}, \end{align*}\] so \(m + o < n + p\). \(\blacksquare\)
Euclidean division is proven in Theorem 1, but the content of the proof is spread over several lemmata, one for each of several cases. The proofs of most of the lemmata follow the same strategy: define a set of non-negative remainders, prove that the set is not empty and invoke Lemma 1 to deduce the existence of a smallest non-negative remainder. The proofs following this strategy are preceded by informal examples to help determine the sign of the quotients \(q\) to consider when defining the set of non-negative remainders.
Lemma 3 For all \(m > 0\) and \(n > 0\), there exist unique \(q \in \symbb{Z}\) and \(0 \leq r \leq \lvert n \rvert - 1\) such that \(m = nq + r\).
As an example, if \(m \overset{!}{=}23\) and \(n \overset{!}{=}5\), then dividng \(m\) by \(n\) can be accomplished by incrementing the quotient from zero: \[\begin{align*} \underbrace{23}_{\overset{!}{=}m} &\overset{!}{=}\underbrace{5}_{\overset{!}{=}n} \cdot \underbrace{0}_{\overset{!}{=}\tilde{q}} + \underbrace{23}_{\overset{!}{=}\tilde{r}}\\[0.75em] &\overset{!}{=}5 \cdot 1 + 18\\[0.75em] &\overset{!}{=}5 \cdot 2 + 13\\[0.75em] &\overset{!}{=}5 \cdot 3 + 8\\[0.75em] &\overset{!}{=}\underbrace{5}_{\overset{!}{=}n} \cdot \underbrace{4}_{\overset{!}{=}q} + \underbrace{3}_{\overset{!}{=}r}. \end{align*}\] Given \(m\) and \(n\), there are two parameters in the statement of Lemma 3: \(q\) and \(r\). This can simplified by focusing primarily on the remainders and rewriting \(m = nq + r\) as \(m - nq = r\). Furthermore, the decreasing sequence of non-negative remainders \(23, 18, 13, 8, 3\) suggests defining a set of non-negative remainders and using well-ordering to identify the smallest such remainder, in this case \(3\), since \(0 \overset{!}{\leq}3 \overset{!}{\leq}\lvert 5 \rvert - 1\).
Proof. Define \(M \coloneq \{ m - nq \colon q \geq 0 \text{ and } m - nq \geq 0 \} \subseteq \symbb{N}\uplus \{ 0 \}\). If \(q = 0\) then \(m - nq = m - n \cdot 0 = m - 0 = m > 0\), so \(M \neq \emptyset\) and by Lemma 1 \(M\) has a least element. Suppose \(q_1 \geq 0\) is such that \(m - nq_1 \in M\) is the least element of \(M\), and set \(r_1 \coloneq m - nq_1\). Because \(r_1 \in M\), by definition \(r_1 \geq 0\). If \(r_1 > \lvert n \rvert - 1 = n - 1\) then by definition \(m - nq_1 > n - 1\), hence \(m + 1 > nq_1 + n = n(q_1 + 1)\). If \(n(q_1 + 1) > m\) then \(m < n(q_1 + 1) < m + 1\), which was proven to be impossible in the Section 1.2.2 notes for Katznelson and Katznelson (2024). Therefore \(m \geq n(q_1 + 1)\), so \(m - n(q_1 + 1) \geq 0\) which implies that \(m - n(q_1 + 1) \in M\). Since \(q_1 + 1 > q_1\), after multiplying both sides by \(-n < 0\) and adding \(m\) to both sides it follows that \(m - n(q_1 + 1) < m - nq_1 = r_1\), which contradicts the assumption that \(r_1\) is the least element of \(M\). Thus \(q_1 \geq 0\) and \(0 \leq r_1 \leq \lvert n \rvert - 1\) and \(nq_1 + r_1 = nq_1 + (m - nq_1) = (nq_1 - nq_1) + m = m\), so \(q_1\) and \(r_1\) satisfy the stated conditions.
Next suppose there exist \(q_2 \in \symbb{Z}\) and \(0 \leq r_2 \leq \lvert n \rvert - 1\) such that \(m = nq_2 + r_2\). If \(r_2 \neq r_1\) then assume without loss of generality that \(r_2 > r_1\). If \(q_2 \geq q_1\) then \(nq_2 \geq nq_1\) and by Lemma 2 \(nq_2 + r_2 > nq_1 + r_1\), which is a contradiction. Therefore \(q_2 < q_1\). If \(q_2 > q_1 - 1\) then it follows that \(q_1 - 1 < q_2 < (q_1 - 1) + 1 = q_1\), which was proven to be impossible in the Section 1.2.2 notes for Katznelson and Katznelson (2024). Hence \(q_2 \leq q_1 - 1\), so \(nq_2 \leq n(q_1 - 1) = nq_1 - n\) and therefore \(nq_2 + r_2 \leq (nq_1 - n) + r_2 = nq_1 + (r_2 - n)\). Since \(r_2 \leq \lvert n \rvert - 1 = n - 1\) implies that \(r_2 - n \leq -1 < 0\), it follows that \(nq_2 + r_2 \leq nq_1 + (r_2 - n) < nq_1 \leq nq_1 + r_1 = m\). This implies that \(nq_2 + r_2 < m\), which is a contradiction. Therefore \(r_2 = r_1\). Using Lemma 1 from Exercise 1.2.1 and the Section 1.2.2 notes, both for Katznelson and Katznelson (2024), \[\begin{align*} 0 &= m - m\\[0.75em] &= (nq_1 + r_1) - (nq_2 + r_2)\\[0.75em] &= (nq_1 + r_1) + (\underbrace{-(nq_2 + r_2)}_{= (-nq_2) + (-r_2)})\\[0.75em] &= (nq_1 - nq_2) + (\underbrace{r_1 - r_2}_{= 0})\\[0.75em] &= n(q_1 - q_2), \end{align*}\] and by assumption \(n \neq 0\), so it follows from Exercise 1.2.9 for Katznelson and Katznelson (2024) that \(q_1 - q_2 = 0\) whence \(q_1 = q_2\), so \(q_1\) and \(r_1\) are unique. \(\blacksquare\)
Lemma 4 For all \(m > 0\) and \(n < 0\), there exist unique \(q \in \symbb{Z}\) and \(0 \leq r \leq \lvert n \rvert - 1\) such that \(m = nq + r\).
As an example, if \(m \overset{!}{=}23\) and \(n \overset{!}{=}-5\), then dividing \(m\) by \(n\) can be accomplished by decrementing \(q\) from zero: \[\begin{align*} \underbrace{23}_{\overset{!}{=}m} &\overset{!}{=}\underbrace{(-5)}_{\overset{!}{=}n} \cdot \underbrace{0}_{\overset{!}{=}\tilde{q}} + \underbrace{23}_{\overset{!}{=}\tilde{r}}\\[0.75em] &\overset{!}{=}(-5) \cdot (-1) + 18\\[0.75em] &\overset{!}{=}(-5) \cdot (-2) + 13\\[0.75em] &\overset{!}{=}(-5) \cdot (-3) + 8\\[0.75em] &\overset{!}{=}\underbrace{(-5)}_{\overset{!}{=}n} \cdot \underbrace{(-4)}_{\overset{!}{=}q} + \underbrace{3}_{\overset{!}{=}r}. \end{align*}\] As the example suggests, the proof of Lemma 4 is similar to the proof of Lemma 3, except that it’s necessary to consider \(q \leq 0\) instead of \(q \geq 0\).
Proof. Define \(M \coloneq \{ m - nq \colon q \leq 0 \text{ and } m - nq \geq 0 \} \subseteq \symbb{N}\uplus \{ 0 \}\). If \(q = 0\) then \(m - nq = m - n \cdot 0 = m - 0 = m > 0\), so \(M \neq \emptyset\) and by Lemma 1 \(M\) has a least element. Suppose \(q_1 \leq 0\) is such that \(m - nq_1 \in M\) is the least element of \(M\), and set \(r_1 \coloneq m - nq_1\). Because \(r_1 \in M\), by definition \(r_1 \geq 0\). If \(r_1 > \lvert n \rvert - 1 = -n - 1\) then by definition \(m - nq_1 > -n - 1\), hence \(m + 1 > nq_1 - n = n(q_1 - 1)\). By the same logic as in the proof of Lemma 3 it follows that \(m \geq n(q_1 - 1)\), so \(m - n(q_1 - 1) \geq 0\) and therefore \(m - n(q_1 - 1) \in M\). Since \(q_1 - 1 < q_1\), after multiplying both sides by \(-n > 0\) and adding \(m\) to both sides it follows that \(m - n(q_1 - 1) < m - nq_1 = r_1\), which contradicts the assumption that \(r_1\) is the least element of \(M\). Thus \(q_1 \leq 0\) and \(0 \leq r_1 \leq \lvert n \rvert - 1\) and \(nq_1 + r_1 = nq_1 + (m - nq_1) = (nq_1 - nq_1) + m = m\), so \(q_1\) and \(r_1\) satisfy the stated conditions.
Next suppose there exist \(q_2 \in \symbb{Z}\) and \(0 \leq r_2 \leq \lvert n \rvert - 1\) such that \(m = nq_2 + r_2\). If \(r_2 \neq r_1\) then assume without loss of generality that \(r_2 > r_1\). If \(q_2 \leq q_1\) then \(nq_2 \geq nq_1\) and by Lemma 2 \(nq_2 + r_2 > nq_1 + r_1\), which is a contradiction. Therefore \(q_2 > q_1\). By similar logic as in the proof of Lemma 3 it follows that \(q_2 \geq q_1 + 1\), so \(nq_2 \leq n(q_1 + 1) = nq_1 + n\) and therefore \(nq_2 + r_2 \leq (nq_1 + n) + r_2 = nq_1 + (r_2 + n)\). Since \(r_2 \leq \lvert n \rvert - 1 = -n - 1\) implies that \(r_2 + n \leq -1 < 0\), it follows that \(nq_2 + r_2 \leq nq_1 + (r_2 + n) < nq_1 \leq nq_1 + r_1 = m\). This implies that \(nq_2 + r_2 < m\), which is a contradiction. Therefore \(r_2 = r_1\). By the same logic as in the proof of Lemma 3 it follows that \(q_1 = q_2\), so \(q_1\) and \(r_1\) are unique. \(\blacksquare\)
Lemma 5 For all \(m < 0\) and \(n > 0\), there exist unique \(q \in \symbb{Z}\) and \(0 \leq r \leq \lvert n \rvert - 1\) such that \(m = nq + r\).
As an example, if \(m \overset{!}{=}-23\) and \(n \overset{!}{=}5\), then dividng \(m\) by \(n\) can be accomplished by decrementing \(q\) from zero: \[\begin{align*} \underbrace{-23}_{\overset{!}{=}m} &\overset{!}{=}\underbrace{5}_{\overset{!}{=}n} \cdot \underbrace{0}_{\overset{!}{=}\tilde{q}} \underbrace{- 23}_{\overset{!}{=}\tilde{r}}\\[0.75em] &\overset{!}{=}5 \cdot (-1) - 18\\[0.75em] &\overset{!}{=}5 \cdot (-2) - 13\\[0.75em] &\overset{!}{=}5 \cdot (-3) - 8\\[0.75em] &\overset{!}{=}5 \cdot (-4) - 3\\[0.75em] &\overset{!}{=}\underbrace{5}_{\overset{!}{=}n} \cdot \underbrace{(-5)}_{\overset{!}{=}q} + \underbrace{2}_{\overset{!}{=}r}. \end{align*}\] As the example suggests, the proof of Lemma 5 is similar to the proofs of Lemma 3 and Lemma 4. The main challenge in the proof of Lemma 5 is proving that the set of non-negative remainders is not empty.
Proof. Define \(M \coloneq \{ m - nq \colon q \leq 0 \text{ and } m - nq \geq 0 \} \subseteq \symbb{N}\uplus \{ 0 \}\). By assumption \(n > 0\), and by similar logic as in the proof of Lemma 3 it follows that \(n \geq 1\). Taking \(q \coloneq m < 0\) and multiplying \(n \geq 1\) by \(q\) on the left side and \(m\) on the right side implies that \(nq \leq m\), so \(m - nq \geq 0\). Thus \(M \neq \emptyset\) and by Lemma 1 \(M\) has a least element. Suppose \(q_1 \leq 0\) is such that \(m - nq_1 \in M\) is the least element of \(M\), and set \(r_1 \coloneq m - nq_1\). Note that if \(q_1 = 0\) then \(r_1 = m - nq_1 = m - n \cdot 0 = m < 0\), which is a contradiction. Therefore \(q_1 < 0\), which implies that \(q_1 \leq -1\). From this point the proof proceeds as in the proof of Lemma 3, except for this proof \(q_1 \leq -1\). \(\blacksquare\)
Lemma 6 For all \(m < 0\) and \(n < 0\), there exist unique \(q \in \symbb{Z}\) and \(0 \leq r \leq \lvert n \rvert - 1\) such that \(m = nq + r\).
As an example, if \(m \overset{!}{=}-23\) and \(n \overset{!}{=}-5\), then dividng \(m\) by \(n\) can be accomplished by incrementing \(q\) from zero: \[\begin{align*} \underbrace{-23}_{\overset{!}{=}m} &\overset{!}{=}\underbrace{(-5)}_{\overset{!}{=}n} \cdot \underbrace{0}_{\overset{!}{=}\tilde{q}} \underbrace{- 23}_{\overset{!}{=}\tilde{r}}\\[0.75em] &\overset{!}{=}(-5) \cdot 1 - 18\\[0.75em] &\overset{!}{=}(-5) \cdot 2 - 13\\[0.75em] &\overset{!}{=}(-5) \cdot 3 - 8\\[0.75em] &\overset{!}{=}(-5) \cdot 4 - 3\\[0.75em] &\overset{!}{=}\underbrace{(-5)}_{\overset{!}{=}n} \cdot \underbrace{5}_{\overset{!}{=}q} + \underbrace{2}_{\overset{!}{=}r}. \end{align*}\]
As in the proof of Lemma 5, the main challenge in the proof of Lemma 6 is proving that the set of non-negative remainders is not empty.
Proof. Define \(M \coloneq \{ m - nq \colon q \geq 0 \text{ and } m - nq \geq 0 \} \subseteq \symbb{N}\uplus \{ 0 \}\). By assumption \(n < 0\), and by similar logic as in the proof of Lemma 3 it follows that \(n \leq -1\). Taking \(q \coloneq -m > 0\) and multiplying \(n \leq -1\) by \(q\) on the left side and \(-m\) on the right side implies that \(nq \leq (-1) \cdot (-m) = m\), so \(m - nq \geq 0\). Thus \(M \neq \emptyset\) and by Lemma 1 \(M\) has a least element. Suppose \(q_1 \geq 0\) is such that \(m - nq_1 \in M\) is the least element of \(M\), and set \(r_1 \coloneq m - nq_1\). Note that if \(q_1 = 0\) then \(r_1 = m - nq_1 = m - n \cdot 0 = m < 0\), which is a contradiction. Therefore \(q_1 > 0\), which implies that \(q_1 \geq 1\). From this point the proof proceeds as in the proof of Lemma 4, except for this proof \(q_1 \geq 1\). \(\blacksquare\)
The proofs of Lemma 7 and Lemma 8 do not require any motivating examples because it is clear that when \(m\) is zero, \(q\) and \(r\) should both be zero.
Lemma 7 For all \(m = 0\) and \(n > 0\), there exist unique \(q \in \symbb{Z}\) and \(0 \leq r \leq \lvert n \rvert - 1\) such that \(m = nq + r\).
Proof. Taking \(q_1 \coloneq 0\) and \(r_1 \coloneq 0\), then \(nq_1 + r_1 = n \cdot 0 + 0 = 0 = m\), so \(q_1\) and \(r_1\) satisfy the stated conditions. Next suppose there exist \(q_2 \in \symbb{Z}\) and \(0 \leq r_2 \leq \lvert n \rvert - 1\) such that \(m = nq_2 + r_2\). If \(r_2 \neq r_1\) then necessarily \(r_2 > r_1\). From this point the proof proceeds as in the proof of Lemma 3. \(\blacksquare\)
Lemma 8 For all \(m = 0\) and \(n < 0\), there exist unique \(q \in \symbb{Z}\) and \(0 \leq r \leq \lvert n \rvert - 1\) such that \(m = nq + r\).
Proof. Taking \(q_1 \coloneq 0\) and \(r_1 \coloneq 0\), then \(nq_1 + r_1 = n \cdot 0 + 0 = 0 = m\), so \(q_1\) and \(r_1\) satisfy the stated conditions. Next suppose there exist \(q_2 \in \symbb{Z}\) and \(0 \leq r_2 \leq \lvert n \rvert - 1\) such that \(m = nq_2 + r_2\). If \(r_2 \neq r_1\) then necessarily \(r_2 > r_1\). From this point the proof proceeds as in the proof of Lemma 4. \(\blacksquare\)
Theorem 1 (Euclidean division) For all \(m \in \symbb{Z}\) and \(n \in \symbb{Z}\setminus \{ 0 \}\), there exist unique \(q \in \symbb{Z}\) and \(0 \leq r \leq \lvert n \rvert - 1\) such that \(m = nq + r\).
Proof. Lemma 3 proves the claim when \(m > 0\) and \(n > 0\). Lemma 4 proves the claim when \(m > 0\) and \(n < 0\). Lemma 5 proves the claim when \(m < 0\) and \(n > 0\). Lemma 6 proves the claim when \(m < 0\) and \(n < 0\). Lemma 7 proves the claim when \(m = 0\) and \(n > 0\). Lemma 8 proves the claim when \(m = 0\) and \(n < 0\). \(\blacksquare\)
The proofs of most of the lemmata comprising Theorem 1 do not suggest a method for computing the quotient and remainder given \(m\) and \(n\), because the proofs hinge on well-ordering to assert the existence of \(q\) and \(r\). However, the informal examples suggest a method to compute the quotient and remainder, and this method is implemented in the Python code below. The function divide_m_by_n() takes a pair of integers \(m\) and \(n\), and first checks if \(m = 0\). If so, divide_m_by_n() is designed to throw an error. Otherwise divide_m_by_n() checks which of the cases in the proof of Theorem 1 is applicable to \(m\) and \(n\). Having found the applicable case, divide_m_by_n() then marches from zero in either the positive or negative direction in steps of size \(q\), computes the remainder \(r\) after every step, and returns \(q\) and \(r\) when \(r\) meets the desired criterion. (If \(m = 0\) then divide_m_by_n() simply returns \(q, r = 0\).)
The for loop uses rng.integers() to randomly draw 10 pairs of integers \(m\) and \(n\) between \(-100\) and \(100\), and then for each pair, the function divide_m_by_n() computes and returns \(q\) and \(r\). The results for each iteration of the for loop are collected in the rows of the results data frame.
import numpy as np
import pandas as pd
# Define parameters
m_low = -100
m_high = 100
n_low = -100
n_high = 100
size = 1
num = 10
def divide_m_by_n(m, n):
# Throw error if n is zero
if (n == 0):
raise Exception("Cannot divide by zero.")
q = 0
r = m - q * n
# Case when m > 0, n > 0
if m > 0 and n > 0:
while r > abs(n) - 1:
q = q + 1
r = m - q * n
return q, r
# Case when m > 0, n < 0
elif m > 0 and n < 0:
while r > abs(n) - 1:
q = q - 1
r = m - q * n
return q, r
# Case when m < 0, n > 0
elif m < 0 and n > 0:
while r < 0:
q = q - 1
r = m - q * n
return q, r
# Case when m < 0, n < 0
elif m < 0 and n < 0:
while r < 0:
q = q + 1
r = m - q * n
return q, r
# Cases when m = 0, n != 0
elif m == 0:
return 0, 0
# Set up the random-number generator
rng = np.random.default_rng()
# Set up the array to hold the results
results = np.empty((num, 5))
for i in range(num):
# Draw m and n
m = rng.integers(
low=m_low,
high=m_high,
size=size
).item()
n = rng.integers(
low=n_low,
high=n_high,
size=size
).item()
# Compute the quotient and remainder
q, r = divide_m_by_n(m=m, n=n)
# Compute nq + r and check that it equals m
nq_plusr = n * q + r
q_and_r = nq_plusr == m
# Check that 0 <= r <= |n| - 1
# r_bounds = (0 <= r) and (r <= abs(n) - 1)
# Store the results in the ith row of results
results[i, :] = [m, n, q, r, nq_plusr]
# Convert results to a data frame
results = pd.DataFrame(results, dtype=int)
# Name the columns of the data frame
results.columns = ['m', 'n', 'q', 'r', 'nq + r']
# Print the dataframe
print(results.to_string(index=False))Just as “division by zero” is informally understood to be impossible, it is necessary that \(n \neq 0\) when dividing \(m\) by \(n\). If \(n = 0\) were permitted then bounding \(r\) between \(0\) and \(\lvert n \rvert - 1\) would not make sense.↩︎