Proof of the The Division Algorithm

[blueberryfive]

This is going to be kind of a long post, and I'm citing the author because it's directly from a textbook, but I'm assuming this proof is standard and I won't be doing anything unethical. I'm basically going to post it with my questions interrupting the text. I'm not sure how he got from some points to others, I'm certain we're going to cover this in class tomorrow (probably quickly). So, here goes.

It comes from Abstract Algebra: A Concrete Introduction by Robert H. Redfield.


"
The division algorithm.

m=nq+r

0$\leq$r<n

Proof:

Let S denote the set of differences m-nx, where x is an integer and m-nx$\geq$0. "

Why does he start in this way? How would you know to begin with a statement like this? Why is x an integer? I feel this I need to understand because much of the proof seems to be manipulation of this statement, and if I don't really grasp it the manipulation seems empty.

"Since n>0, n$\geq1$ and hence -n$\geq$-1."

Why is n>0? He says "since" which implies that it's something that's been previously established; I see n>r, and also r$\geq$0, but I don't know that n is necessarily >0. Or could you?

"Then m$\geq$-$\left|m\right|$$\geq$-n$\left|m\right|$=n(-$\left|m\right|$)..."

Okokok. He says "Then", so I'm assuming this must follow from the directly preceding statement, but how? Isn't a number always greater than or equal to its negative absolute value? Why would he say "Then", then? Is the fact that a number is greater than or equal to its negative absolute value just a preliminary statement that doesn't necessarily depend on the last sentence--just to set up the fact that multiplying the previous equation through by the absolute value of m depended on, well, the previous sentence?

"...so that m-n(-$\left|m\right|$) $\in$S, i.e. S is not empty."

Why is it important that S is non empty? This probably seems very basic to someone who has studied this stuff but it's not particularly clear to me.

"So since S is bounded below by 0, the well ordering principle implies that S contains a minimal element r, and since r$\in$S, 0$\leq$r and m=nq+r for some integer q."

It's bounded below by 0 because he said the set S consists of m-nx$\geq$0, right?

When he invokes r, is it the same r from the theorem statement. In other words, is he talking about the r that we know is between 0 and n, or is he conveniently choosing r, as if its just some number, and then showing that it will, in fact be that r in the theorem? Does this question make any sense?

"It remains to show that r<n."

Why? If r<n, what does this accomplish?

Suppose by way of contradiction that r$\geq$n. Then r-n=m-nq-n=m-n(q+1) and r-n$\geq$0 so that r-n$\in$S. But, since r-n<r, this contradicts our assumption that r is minimal, and hence we may conclude that r<n."

This seems alright. So, I suppose the actual mechanics of the proof seem understandable...mostly just algebra, but I don't really understand why he does what he does. Should I drop this course, or is this natural?

Thanks,

B

 

[blueberryfive]

He says suppose n>0 before he starts the proof. Hadn't seen it.

 

[micromass]

This is going to be kind of a long post, and I'm citing the author because it's directly from a textbook, but I'm assuming this proof is standard and I won't be doing anything unethical. I'm basically going to post it with my questions interrupting the text. I'm not sure how he got from some points to others, I'm certain we're going to cover this in class tomorrow (probably quickly). So, here goes.

It comes from Abstract Algebra: A Concrete Introduction by Robert H. Redfield."
The division algorithm.

m=nq+r

0$\leq$r<n

Proof:

Let S denote the set of differences m-nx, where x is an integer and m-nx$\geq$0. "

Why does he start in this way? How would you know to begin with a statement like this?

He wants to find q and r such that m=nq+r. Thus he wants to find q and r such that m-nq=r. This urges us to look at the set of all m-nx with x an integer. Because we want $0\leq r<n$, it follows that wa want to choose r minimal. In order to prove that such an r minimal exist, we must prove that the set of all m-nx has a minimum. And we prove this by the well-ordering theorem.

Why is x an integer?

Because we choose x that way.

Since n>0, n$\geq1$ and hence -n$\geq$-1."

Why is n>0? He says "since" which implies that it's something that's been previously established; I see n>r, and also r$\geq$0, but I don't know that n is necessarily >0. Or could you?

n>r and $r\geq 0$, this implies that n>0.

"Then m$\geq$-$\left|m\right|$$\geq$-n$\left|m\right|$=n(-$\left|m\right|$)..."

Okokok. He says "Then", so I'm assuming this must follow from the directly preceding statement, but how? Isn't a number always greater than or equal to its negative absolute value? Why would he say "Then", then? Is the fact that a number is greater than or equal to its negative absolute value just a preliminary statement that doesn't necessarily depend on the last sentence--just to set up the fact that multiplying the previous equation through by the absolute value of m depended on, well, the previous sentence?

The statement $m\geq -|m|$ follows immediately. The "since" is there for the next inequality. I.e. in order to prove $-|m|\geq -n|m|$. To prove this, we need to know that $-1\geq -n$.

"...so that m-n(-$\left|m\right|$) $\in$S, i.e. S is not empty."

Why is it important that S is non empty? This probably seems very basic to someone who has studied this stuff but it's not particularly clear to me.

We want to prove that S has a minimum. We want to prove it by invoking the well-ordering theorem. But in order to invoke this, we need to prove that S is non-empty. Indeed, the well-ordering theorem says that every non-empty bounded-below set has a minimum.

"So since S is bounded below by 0, the well ordering principle implies that S contains a minimal element r, and since r$\in$S, 0$\leq$r and m=nq+r for some integer q."

It's bounded below by 0 because he said the set S consists of m-nx$\geq$0, right?

Right.

When he invokes r, is it the same r from the theorem statement. In other words, is he talking about the r that we know is between 0 and n, or is he conveniently choosing r, as if its just some number, and then showing that it will, in fact be that r in the theorem? Does this question make any sense?

He is conveniently choosing r and he shows that it is the r of the theorem.

"It remains to show that r<n."

Why? If r<n, what does this accomplish?

Well, we must show that our r is indeed the r from the theorem. In order to show this, we must show three things:

• m=nq+r for a certain q.
• $r\geq 0$
• r<n

Only the last points has not yet been proven (the other two points follow from the choice of our r). So we must only still prove that r<n.

Suppose by way of contradiction that r$\geq$n. Then r-n=m-nq-n=m-n(q+1) and r-n$\geq$0 so that r-n$\in$S. But, since r-n<r, this contradicts our assumption that r is minimal, and hence we may conclude that r<n."

This seems alright. So, I suppose the actual mechanics of the proof seem understandable...mostly just algebra, but I don't really understand why he does what he does. Should I drop this course, or is this natural?

Thanks,

B

 

[blueberryfive]

Thanks a lot.