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.(adsbygoogle = window.adsbygoogle || []).push({});

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

"

The division algorithm.

m=nq+r

0[itex]\leq[/itex]r<n

Proof:

Let S denote the set of differences m-nx, where x is an integer and m-nx[itex]\geq[/itex]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[itex]\geq1[/itex] and hence -n[itex]\geq[/itex]-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[itex]\geq[/itex]0, but I don't know that n is necessarily >0. Or could you?

"Then m[itex]\geq[/itex]-[itex]\left|m\right|[/itex][itex]\geq[/itex]-n[itex]\left|m\right|[/itex]=n(-[itex]\left|m\right|[/itex])..."

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(-[itex]\left|m\right|[/itex]) [itex]\in[/itex]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[itex]\in[/itex]S, 0[itex]\leq[/itex]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[itex]\geq[/itex]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[itex]\geq[/itex]n. Then r-n=m-nq-n=m-n(q+1) and r-n[itex]\geq[/itex]0 so that r-n[itex]\in[/itex]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

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Proof of the The Division Algorithm

**Physics Forums | Science Articles, Homework Help, Discussion**