Division Algorithm: What is the set "S", and where does "a - bk" come from?

[jpanknin]

I'm going over the proof for the Division Algorithm (given below for reference). In the proof for the Division Algorithm, it says, "Consider the set S = {a - bk | k is an integer and a - bk >= 0}. My question is where does the set S and, more specificially, [imath]a - bk[/imath] come from? At this point it seems like an arbitrary choice of an expression to prove the theorem.

More generally, I often struggle to see the significance of examples in proofs like this. Why do we just let something be something in a proof? It seems like there would be a rhyme or reason.

 

[Dr.Peterson]

I'm going over the proof for the Division Algorithm (given below for reference). In the proof for the Division Algorithm, it says, "Consider the set S = {a - bk | k is an integer and a - bk >= 0}. My question is where does the set S and, more specificially, [imath]a - bk[/imath] come from? At this point it seems like an arbitrary choice of an expression to prove the theorem.

More generally, I often struggle to see the significance of examples in proofs like this. Why do we just let something be something in a proof? It seems like there would be a rhyme or reason.

View attachment 36510

View attachment 36512

Well, yes, the set S was defined as it is in order to prove the theorem. But not arbitrarily. Reading the proof ought to reveal how it contributes, and therefore why one would want to use it. There is reason (and maybe it even "rhymes" with other proofs you've seen).

You are perhaps asking how one would come up with that idea. It's unfortunate that, often, proofs are stated in a form that gives no clue to how they would have been invented; if I wrote a book for students with little experience with proofs, I would probably want to preface such a proof with some explanation of how you would think of it. But in the absence of such an explanation, you can work backward from the proof to the reasoning that may lie behind it. And that exercise can be very useful in getting a deeper understanding of the proof itself.

So try doing that. Think about what in the proof itself might have motivated that choice. Then show us the proof, along with your thoughts, and we may be able to make additional suggestions.

By the way, one way to think through the meaning of the proof might be to walk through it with a specific example, say dividing 7 by 3 or something. List set S for that example, and so on. This is good in general for understanding any proof.

 

[Steven G]

I'm going over the proof for the Division Algorithm (given below for reference). In the proof for the Division Algorithm, it says, "Consider the set S = {a - bk | k is an integer and a - bk >= 0}. My question is where does the set S and, more specificially, [imath]a - bk[/imath] come from? At this point it seems like an arbitrary choice of an expression to prove the theorem.

More generally, I often struggle to see the significance of examples in proofs like this. Why do we just let something be something in a proof? It seems like there would be a rhyme or reason.

View attachment 36510

View attachment 36512

If you look at the statement of the theorem it talks about a=bq +r, well replacing q with k we have a=bk+r. Then a-bk = r. Maybe we need r to be positive? Maybe we need to think of all values for k such that a-bk>0.
As Dr Peterson said, work backwards to see why you need this set S.

Please post back with your thoughts and we can discuss it.

 

[jpanknin]

You are perhaps asking how one would come up with that idea. It's unfortunate that, often, proofs are stated in a form that gives no clue to how they would have been invented; if I wrote a book for students with little experience with proofs, I would probably want to preface such a proof with some explanation of how you would think of it. But in the absence of such an explanation, you can work backward from the proof to the reasoning that may lie behind it. And that exercise can be very useful in getting a deeper understanding of the proof itself.

Yes, this is exactly what my confusion is. It seems that S = {a - bk | k is an integer and a - bk >= 0} has nothing to do with a = bq + r. Some preface, as you say, would be really helpful because it seems like a - bk was chosen randomly. Like "Let x = yellow, then it follows that the proof is correct." Why yellow? Why not greed or red or fuchsia?

I've watched several videos that walk through it with examples and they use the same definition of S. They also work through some examples and I think I get the computational application.

 

[Steven G]

OK, you looked at some videos. Now you need to think about this on your own. This might take minutes, hours or even days before it clicks. Someone explaining this to you might not help. I myself, while in graduate school, certainly spend at least five days thinking about a problem. Then it just clicked and I would see it. For you right now it is easier because you have the proof in front of you.

 

[Dr.Peterson]

Yes, this is exactly what my confusion is. It seems that S = {a - bk | k is an integer and a - bk >= 0} has nothing to do with a = bq + r. Some preface, as you say, would be really helpful because it seems like a - bk was chosen randomly. Like "Let x = yellow, then it follows that the proof is correct." Why yellow? Why not greed or red or fuchsia?

I've watched several videos that walk through it with examples and they use the same definition of S. They also work through some examples and I think I get the computational application.

Show us the proof, and even one little thought about it, and we can probably point out something to focus on.

For example, where in the proof do those two things you say are unrelated come closest to one another?

 

[blamocur]

If you look at the statement of the theorem it talks about a=bq +r, well replacing q with k we have a=bk+r. Then a-bk = r.

I'd add that now we know that [imath]S[/imath] is a set of all possible non-negative values for [imath]r[/imath]. Can you show that there is exactly one element there which satisfies the theorem?

 

[Steven G]

We know that a=qb+r. Now in long division we want to pick the largest q (quotient) but that causes r to be the smallest!!

Consider this: 3 goes into 23, 6 times remainder 5 (ie 23 = 6*3+5). Now we can make q larger by letting q=7. Now we can say that 3 goes into 23, 7 times remainder 2.

Since a=bq+r implies that r = a-bq is the motivation to find the smallest that a-bx can be where x is an integer and a-bx>0.

This is strong motivation to define S = {a-bx| x is an integer and a-bx>0} and find the smallest member of S.


I think that this explanation has more than made up for any errors, typos ... for the past year

 

[Steven G]

Here is a video that you should like.