# Division Algorithm proof explanation

• SithsNGiggles
In summary, the Division Algorithm states that for any integer a and positive integer b, there exists a unique representation of a as qb+r where 0 \leq r < b. This is proven by defining a set S, which contains all the possible representations of a as a+xb, and using the Well Ordering Principle to show that there exists a least element r in S. The proof also shows that if r \geq b, then we can find a smaller element in S, which contradicts the minimality of r. This justifies the use of the set S and ultimately proves the uniqueness of the representation of a.
SithsNGiggles
This is taken from "Passage to Abstract Mathematics," Watkins and Meyer.

"Theorem 2.3.9 (Division Algorithm) If $a \in\mathbb{Z}$ and $b\in\mathbb{N}$, then there exist $q,r \in\mathbb{Z}$ such that $a = qb+r$ and $0 \leq r < b$.
Furthermore, for each $b\in\mathbb{N}$, this representation of $a$ is unique.

Proof.
Let $a\in\mathbb{Z}$ and $b\in\mathbb{N}$ be given, and let $S = \{ a + xb : x\in\mathbb{Z} \wedge a+xb\geq 0 \}$.

Note that there is an element in $S$. (If $a\geq 0$, pick $x=0$, so that $a\in S$; if $a<0$, pick $x=-a$, so that $a-ab = a(1-b) \in S$.) Thus, by the Well Ordering Principle, $S$ has a least element, which we denote by $r$. Since $r \in S, r=a-qb$ for some $q\in\mathbb{Z}$.
By definition, $r \geq 0$.

Suppose that $r \geq b$. Then,
$a - (q+1)b = a - qb - b = r - b \geq 0$,
and $a-(q+1)b = r-b<r$, since $b>0$. This gives an element $r-b\in S$ which is strictly less than $r$, contradicting the minimality of $r$. Thus $r<b$. This yields the representation $a=qb+r$ with $0\leq r < b$..."​

(The rest of the proof concerns the uniqueness of the representation, which I understand somewhat.)

I was hoping someone could help explain the red text. My main questions are
• What is the advantage to using the set $S$? Or, in other words, why is this set used?
• What is the "Note that ... (If $a\leq 0$...)" saying? I don't really see what's going on here.
• How do we know that $r=a-qb$?

I think once these questions are addressed I'll be better equipped in understanding the proof overall. Thanks!

The bit in the parentheses is establishing that the the set S is nonempty. This needs to be known so that the well ordering principle can give us an element r to work with.

We know that r = a-qb since r is an element of S. You may be thinking "doesn't S have elements that look like a+xb?" It does, but we can put x = -q and have our desired representation.

I think that proof goes through every detail, and if I were you, I'd stare at it until it makes sense.

If you're not convinced that you need to use a set like S, try to write the proof without it. (I'm not suggesting you won't be able to)

So I've been looking over this proof and throwing bits of it around in my head for a bit. I've got two more questions:

• Since $a + xb \geq 0$, don't we already know that $0\in S$, or is that only if we're specifically told that $a=0$?
• Where does the $a - (q+1)b$ come from? I don't understand where $q+1$ comes from, specifically.

SithsNGiggles said:
So I've been looking over this proof and throwing bits of it around in my head for a bit. I've got two more questions:

• Since $a + xb \geq 0$, don't we already know that $0\in S$, or is that only if we're specifically told that $a=0$?
• Where does the $a - (q+1)b$ come from? I don't understand where $q+1$ comes from, specifically.

1: Let's look at the case when a=7 and b=2. Then a+xb = 7+2x. Keeping in mind that x is an integer, we see that there's no x that makes 7+2x = 0. So, in this case, 0 is not in S. Ask yourself when 0 will be in S.

----------

2: Still with a=7 and b=2, the division algorithm gives us 7= (3)2 + (1).

Let's say that you're fiddling around with this (without knowing the division algorithm). Maybe you stumble upon the expression 7 = (2)2 + (3) [note that here q=2 and r=3]. Now, 3 is not less than 2, so this seems to go against the division algorithm. Is this division algorithm wrong or can we fix it?

Well, we can just bump up q to 3 (=2+1). This is all that part of the proof is doing. It's establishing that we can find an r between 0 and b.

SithsNGiggles said:
[*]Since $a + xb \geq 0$, don't we already know that $0\in S$, or is that only if we're specifically told that $a=0$?
$0\in S$ if and only if $\exists$ x s.t. a+xb=0. Clearly that will only be the case if b divides a.
[*]Where does the $a - (q+1)b$ come from? I don't understand where $q+1$ comes from, specifically.
r is defined as the least element in S. q is then defined in terms of r, q+1 in terms of q, and finally a - (q+1)b in terms of that. The result is to show that if r >= b then we can construct a smaller member than r.

Benn said:
1: Let's look at the case when a=7 and b=2. Then a+xb = 7+2x. Keeping in mind that x is an integer, we see that there's no x that makes 7+2x = 0. So, in this case, 0 is not in S. Ask yourself when 0 will be in S.

Okay, I see that now. I also reread the beginning and noticed that the proof starts off with letting a being given, so I think that answers my question.

Benn said:
2: Still with a=7 and b=2, the division algorithm gives us 7= (3)2 + (1).

Let's say that you're fiddling around with this (without knowing the division algorithm). Maybe you stumble upon the expression 7 = (2)2 + (3) [note that here q=2 and r=3]. Now, 3 is not less than 2, so this seems to go against the division algorithm. Is this division algorithm wrong or can we fix it?

Well, we can just bump up q to 3 (=2+1). This is all that part of the proof is doing. It's establishing that we can find an r between 0 and b.

Ah, alright. I see what's going on now, but I still need some time to digest all this information and put it all together. Thanks to both of you for the help!

## 1. What is the division algorithm?

The division algorithm is a mathematical concept that states that given two integers, a dividend and a non-zero divisor, there exists a unique quotient and remainder. This means that when dividing one integer by another, there is always a result that can be expressed as a whole number with a remainder.

## 2. What is the purpose of proving the division algorithm?

The proof of the division algorithm serves to formally establish its validity and to provide a logical explanation for its use in solving mathematical problems. It also helps to demonstrate the fundamental principles of division and the relationships between integers.

## 3. How is the division algorithm proven?

The division algorithm is typically proven using mathematical induction, which involves showing that the statement holds true for a base case and then proving that it also holds true for the next case. This process is repeated until it is shown to be true for all possible cases, thus proving the algorithm.

## 4. Why is the division algorithm important in mathematics?

The division algorithm is important because it allows us to perform division with integers, which is a fundamental operation in mathematics. It also serves as the basis for other mathematical concepts, such as the Euclidean algorithm and modular arithmetic. Additionally, understanding and being able to apply the division algorithm is essential in solving many real-world problems.

## 5. Are there any limitations or exceptions to the division algorithm?

Yes, there are some limitations to the division algorithm. It only applies to integers and does not work for dividing other types of numbers, such as fractions or decimals. Additionally, the divisor must be non-zero, otherwise the algorithm is undefined. There are also certain cases, such as dividing by zero, where the division algorithm does not hold true.

Replies
1
Views
853
Replies
1
Views
894
Replies
3
Views
963
Replies
3
Views
951
Replies
1
Views
720
Replies
9
Views
2K
Replies
2
Views
703
Replies
3
Views
1K
Replies
3
Views
542
Replies
15
Views
3K