7
$\begingroup$

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

  1. $a = bq + r$
  2. $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

  1. $a = bq + r$
  2. $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

  1. $a = bq_k + r_k$
  2. $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

  1. $a = bq_k + r_k$
  2. $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.

$\endgroup$
2
  • 3
    $\begingroup$ I think your proof is correct. I haven't read it carefully since I think it is more complex than necessary. All you have to do is observe that $b$ must lie between a unique pair of consecutive integer multiples of $a$, with a weak inequality on one side. $\endgroup$ Jan 23 at 22:39
  • 3
    $\begingroup$ Your new proof looks mostly correct, except for the part where you reduce $a < 0$ to the $a \geq 0$ case, in which you need to pay special attention to the case where $a$ is an integer multiple of $b$. Also I believe that this might be doable in a lot fewer words. $\endgroup$
    – Magma
    Jan 23 at 22:39

2 Answers 2

4
$\begingroup$

Here's a cleaned-up version of this proof:

Let $a, b \in \mathbb R$ with $b \neq 0$.

Existence: If $b > 0$, choosing $q := \lfloor a/b\rfloor$ and $r := a-bq$ yields an integer $q$ with $a/b - 1 < q \leq a/b$, so since $b > 0$ we get $r = a - bq \geq a - b(a/b) = a - a = 0$ and $r = a - bq < a-b(a/b - 1) = b$, in summary $0 \leq r < b$ as desired.

If $b < 0$, then let $a = (-b)q' + r$ with integer $q'$ and $0 \leq r < |{-b}|$, this exists by the "$b > 0$" case. Then if we let $q := -q'$, we find that $q$ is also an integer and $0 \leq r < |{-b}| = |b|$.

Uniqueness: Let $a = bq+r$ and $a = bq'+r'$ such that $q, q'$ are integers and $0 \leq r, r' < |b|$. If $q \neq q'$, then $1 \leq |q-q'|$, so $|b| \leq |bq - bq'| = |a - r - a + r'| = |r - r'|$, in contradiction to $|r - r'| < |(|b| - 0)| = |b|$. So $q = q'$ must have been true, in which case $r = a - bq = a - bq' = r'$ shows that both solutions were the same after all.

Note that these arguments don't rely on terms like divisors of real numbers or repetition of some process, only on simple properties of real numbers, the floor function and absolute values.

$\endgroup$
7
  • $\begingroup$ Thanks, that helps! What is the distinction between $=$ and $:=$? $\endgroup$
    – joseville
    Jan 24 at 0:19
  • 1
    $\begingroup$ @joseville: := is a definition, = is an equality. := should mean that the left-hand side is defined as the right-hand side. It helps, because it means you don't have to look back to see where this definition is coming from. It is the definition. At least, that's the way I understand it. Don't ask me why := has been used for r and not for q, though. math.stackexchange.com/q/25214/386794 $\endgroup$ Jan 24 at 9:29
  • 2
    $\begingroup$ @EricDuminil It wasn't used for q because I forgot to use it there. $\endgroup$
    – Magma
    Jan 24 at 11:34
  • 1
    $\begingroup$ @joseville: I think you can deduce that $a - d < b - c $ and $c - b < d - a$, but don't get enough information to compare $b - d$ and $a - c$. $\endgroup$ Jan 24 at 21:35
  • 1
    $\begingroup$ @joseville Usually when I manipulate inequalities I already know the initial and final inequalities I have and need, so filling in the details in between is just an exercise in moving things around productively. For simple inequalities like this you can just imagine the terms as measurements of certain constructions. For example, in this case, I imagined a line segment of length $a$ being chopped up into $q$ pieces of length $b$ with a bit of length $r$ remaining. Just changing the way I measure, e.g. changing my unit of length from $1$ to $b$, has a nice correspondence to symbol manipulation. $\endgroup$
    – Magma
    Jan 25 at 20:07
2
$\begingroup$

Following @EthanBarker's comment and @Magma's answer's format.

Can someone confirm this proof is also correct?


Let $a, b \in \mathbb R$ with $b \neq 0$.

Existence: There exists consecutive multiples of $b$ such that $a$ lies between said multiples.

If $b > 0$, then there exists $q \in \mathbb Z$ such that $bq \leq a < b(q+1)$. Subtract $bq$ from all sides to get $0 \leq a - bq < b = \lvert b \rvert$.

If $b < 0$, then there exists $q \in \mathbb Z$ such that $bq \leq a < b(q-1)$. Subtract $bq$ from all sides to get $0 \leq a - bq \leq -b = \lvert b \rvert$.

In either case, let $r := a - bq$, then we have shown that there exists integer $q$ and real $r$ such that $a = bq + r$ and $0 \leq r < b = \lvert b \rvert$. $\Box$

Uniqueness: If $b > 0$, let $a$ lie in the real interval $\big[bq, b(q+1)\big)$ such that $a = bq + r$. We already showed that this guarantees $0 \leq r < \lvert b \rvert$. Let $m$ and $n$ be two integers. Two intervals $\big[bm, b(m+1)\big)$ and $\big[bn, b(n+1)\big)$ intersect iff $m = n$ (in fact they are the same interval in that case) and are disjoint otherwise. This means that each real number can belong to at most one such interval. $a$ can only belong to the interval defined by $q$, thus $q$, and by extension, $r$, are unique.

If $b < 0$, let $a$ lie in the real interval $\big[bq, b(q-1)\big)$ such that $a = bq + r$. We already showed that this guarantees $0 \leq r < \lvert b \rvert$. As before, each real number can belong to at most one such interval. $a$ can only belong to the interval defined by $q$, thus $q$, and by extension, $r$, are unique. $\Box$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.