Euclidean division theorem states
Given an integer dividend $a \in \mathbb Z$ and a nonzero integer divisor $b \in \mathbb Z_{\neq 0}$, there exists a unique pair of integer quotient $q \in \mathbb Z$ and integer remainder $r \in \mathbb Z$ that satisfy
- $a = bq + r$
- $0 \leq r < \lvert b \rvert$
I was reading through the existence and uniqueness proof in the Wikipedia article for Euclidean division (entire proof at the bottom) and was wondering which parts of the proof require $a$ and $b$ to be integers. Below is an excerpt of the existence proof and an excerpt of the uniqueness proof that seem to be the only parts of the proof that need either or both of $a$ and $b$ to be integers.
I am trying to extend the proof to allow real-valued dividend $a$ and divisor $b$. The extended theorem would be
Given an real dividend $a \in \mathbb R$ and a nonzero real divisor $b \in \mathbb R_{\neq 0}$, there exists a unique pair of integer quotient $q \in \mathbb Z$ and real remainder $r \in \mathbb R$ that satisfy
- $a = bq + r$
- $0 \leq r < \lvert b \rvert$
Existence proof excerpt
As there are only $r_1$ non-negative integers less than $r_1$, one only needs to repeat this process at most $r_1$ times to reach the final quotient and the remainder. That is, there exist a natural number $k ≤ r_1$ such that $a = bq_k + r_k$ and $0 ≤ r_k < |b|$.
This part of the proof considers integers $a \geq 0$ and $b > 0$. It is shown earlier in the proof that the other cases of $a$ and $b$ (i.e. negative $a$ and/or negative $b$) reduce to this case.
This part can be modified to admit real dividend $a \in \mathbb R$ and nonzero real divisor $b \in \mathbb R_{\neq 0}$. Each time the process is repeated $q$ increases by one − we start with $q_1 = 0$ and have $q_{i+1} = q_i + 1$, so $q_2 = 1$, $q_3 = 2$, etc. In general $q_i = i-1$ and $r_i = a - (i-1)b$. Note, $q_i$ is always an integer while $r_i$ may be real. We need to reach a pair of values $q_k, r_k$ such that
- $a = bq_k + r_k$
- $0 \leq r_k < \lvert b \rvert$
Let $q_k = \big\lfloor \frac{a}{b} \big\rfloor$. By 1., we have
$$r_k = a - bq_k$$
By definition of the floor function, we have
$$\frac{a}{b} \geq \Big\lfloor \frac{a}{b} \Big\rfloor > \frac{a}{b} - 1,$$
which we can rewrite as
$$ \begin{aligned} \frac{a}{b} \geq q_k &> \frac{a}{b} - 1\\ a \geq bq_k &> a - b &&\qquad(\times b)\\ -a \leq -bq_k &< b - a &&\qquad(\times (-1))\\ 0 \leq a - bq_k &< b &&\qquad(+a)\\ 0 \leq r_k &< b \end{aligned} $$
which satisfies 2.. None of this requires $a$ nor $b$ to be integers though (only that $b \neq 0$), so given a real dividend $a \in \mathbb R$ and a nonzero real divisor $b \in \mathbb R_{\neq 0}$, there exists integer $q \in \mathbb Z$ and $r \in [0, \lvert b \rvert) \subset \mathbb R$ such that $a = bq + r$.
Uniqueness proof excerpt
Subtracting the two equations yields $$b(q – q′) = r′ – r.$$ So $b$ is a divisor of $r′ – r$. As $$|r′ – r| < |b|$$ by the above inequalities, one gets $$r′ – r = 0,$$
requires $b$ to be an integer, specifically "$b$ is a divisor of $r' - r$"; however, a different form of reasoning removes this requirement.
As before, let $q_k = \big\lfloor \frac{a}{b} \big\rfloor$. We've already proved that this value of $q_k$ satisfies
- $a = bq_k + r_k$
- $0 \leq r_k < \lvert b \rvert$
even if $a$ and $b$ are real numbers (provided $b \neq 0$).
We will also continue to use $q_i = i-1$ and $r_i = a - (i-1)b$.
Let $j \neq k$ be a positive integer not equal to $k$.
Note, since $j, k \in \mathbb Z$, we have $k-j \in \mathbb Z$.
If $j < k$, we have
$$ \begin{aligned} &j < k\\ \rightarrow &k-j > 0\\ \rightarrow &k-j \geq 1 \end{aligned} $$
where we have used the fact that since $k{-}j$ is an integer and $k{-}j > 0$, we have $k{-}j \geq 1$ ($k{-}j$ cannot equal $0$, the next possible value is $1$).
Similarly, if $j > k$, we have same logic except with the inequality signs flipped
$$ \begin{aligned} &j > k\\ \rightarrow &k-j < 0\\ \rightarrow &k-j \leq -1 \end{aligned} $$
where we have used the fact that since $k{-}j$ is an integer and $k{-}j < 0$, we have $k{-}j \leq -1$ ($k{-}j$ cannot equal $0$, the previous possible value is $-1$).
So, if $j < k$, we have $k{-}j \geq 1$, but if $j > k$, we have $k{-} \leq -1$.
Now, we have
$$ \begin{aligned} r_j - r_k &= a - (j-1)b - (a - (k-1)b)\\ r_j - r_k &= -(j-1)b + (k-1)b\\ r_j - r_k &= (1 - j + k - 1)b\\ r_j - r_k &= (k-j)b\\ r_j &= \underbrace{r_k}_{\in [0, \lvert b \rvert) \subset \mathbb R} + (k{-}j)b \end{aligned} $$
If $j < k$, then $k{-}j \geq 1$ and we have
$$r_j = \underbrace{r_k}_{\in [0, \lvert b \rvert) \subset \mathbb R} + \underbrace{(k{-}j)b}_{\geq b}$$
In this case, the minimum value of $r_j$ is $b$, therefore $r_j \geq b$ which cannot satisfy 2.: $0 \leq r_j < \lvert b \rvert$.
If $j > k$, then $k{-}j \leq -1 \leftrightarrow j{-}k \geq 1$ and we have
$$ \begin{aligned} r_j &= r_k + (k{-}j)b\\ &= \underbrace{r_k}_{\in [0, \lvert b \rvert) \subset \mathbb R} - \underbrace{(j{-}k)b}_{\geq b} \end{aligned} $$
In this case, the maximum value of $r_j$ is $0$, therefore $r_j \leq 0$ which cannot satisfy 2.: $0 \leq r_j < \lvert b \rvert$.
Are these modifications valid?
Entire Proof
Existence
Consider first the case $b < 0$. Setting $b' = –b$ and $q' = –q$, the equation $a = bq + r$ may be rewritten as $a = b'q' + r$ and the inequality $0 ≤ r < |b|$ may be rewritten as $0 ≤ r < |b′|$. This reduces the existence for the case $b < 0$ to that of the case $b > 0$.
Similarly, if $a < 0$ and $b > 0$, setting $a' = –a, q' = –q – 1$, and $r' = b – r$, the equation $a = bq + r$ may be rewritten as $a' = bq' + r′$, and the inequality $0 ≤ r < |b|$ may be rewritten as $0 ≤ r' < |b|$. Thus the proof of the existence is reduced to the case $a ≥ 0$ and $b > 0$ — which will be considered in the remainder of the proof.
Let $q_1 = 0$ and $r_1 = a$, then these are non-negative numbers such that $a = bq_1 + r_1$. If $r_1 < b$ then the division is complete, so suppose $r_1 ≥ b$. Then defining $q_2 = q_1 + 1$ and $r_2 = r_1 – b$, one has $a = bq_2 + r_2$ with $0 ≤ r_2 < r_1$. As there are only $r_1$ non-negative integers less than $r_1$, one only needs to repeat this process at most $r_1$ times to reach the final quotient and the remainder. That is, there exist a natural number $k ≤ r_1$ such that $a = bq_k + r_k$ and $0 ≤ r_k < |b|$.
This proves the existence and also gives a simple division algorithm for computing the quotient and the remainder. However, this algorithm is not efficient, since its number of steps is of the order of $a/b$.
Uniqueness
The pair of integers $r$ and $q$ such that $a = bq + r$ is unique, in the sense that there can't be other pair of integers that satisfies the same condition in the Euclidean division theorem. In other words, if we have another division of $a$ by $b$, say $a = bq' + r'$ with $0 ≤ r' < |b|$, then we must have that
$$q' = q \text{ and } r' = r.$$
To prove this statement, we first start with the assumptions that
$$ 0 ≤ r < |b|\\ 0 ≤ r' < |b|\\ a = bq + r\\ a = bq' + r' $$
Subtracting the two equations yields $$b(q – q′) = r′ – r.$$ So $b$ is a divisor of $r′ – r$. As $$|r′ – r| < |b|$$ by the above inequalities, one gets $$r′ – r = 0,$$
and
$$b(q – q′) = 0.$$
Since $b \neq 0$, we get that $r = r′$ and $q = q′$, which proves the uniqueness part of the Euclidean division theorem.
