(Abstract Algebra 1) The Division Algorithm

A proof of the division algorithm using the well-ordering principle.

[anamtaj]

Thank you so much for this ! I have spent 2 days trying to understand my professor's proof on this but couldn't understand a thing.Your explanation makes it so clear. I will continue watching your videos throughout the semester to help me pass.
Thanks a ton ! Lot of appreciations! Keep these videos coming !

[cm]

The only part that tripped me up was on the uniqueness part, where we were able to squeeze (q' - q)b in between 0 and b:

0 <= (q' - q)b < b

I could see why it's greater than or equal to zero, but I couldn't immediately tell why we could say that it was less than b.

I believe it's because we showed before that b is greater than r:

b > r

If b is greater than r, and now we're assuming r is greater than r', then surely b is greater than r - r':

b > r > r - r'

Since r - r' = (q' - q)b, we can say b is greater than all of that:

b > r > ( r - r' = (q' - q)b )

Simplifying that down:

b > (q' - q)b

If I'm wrong then someone please correct me. If not then I hope this helps someone else.

[simonherrera]

Thank you for this proof. At times it was really hard to follow but I was able to understand the concept behind it.

[EarthandHabitants]

Thanks for this.
You make my life easier. In our class lectures I don't understand a thing while in your simple and concise explanation I understand a lot. :-)

[hayley]

very clear explanation, thank you! I was completely lost since my prof gave us a worksheet to prove the theorem with absolutely no thanks!!!!

[AKM-bw]

I watched some of the videos about the topic you were discussing about. But tbh this video is so simple and easy to understand for beginners like me. Thank you so much sir. Keep the good work. Love from India.

[souverainer]

How do we know that r is the least element of S? It is stated/assumed without proof. All we show is that r>=0 and r<b.

[nicholascousar]

At 10:30, does n have to be 2a? Wouldn't the properties for membership of our set S still be satisfied if we chose n=a? That way, when a<0, a-ab = a(1-b) >=0 because the least this expression can be is 0 (in the case when b=1). All other possible values of b will evaluate to strictly positive integers. So in either case, S is non-empty.

[Xardas_]

at 3:00, if you didn't ignore the negatives if would have worked, as the remainder will be -3 instead of 3. Therefore -21 = (-2) * 9 -3, which is correct. Great video btw. Thank you

[ssbsnb]

in the existence portion of the proof, where does the 2a come from? Could we have chosen a, 3a, 100a, and so on?

[levinkwong]

Do not understand why (q' - q)b < b, you mentioned b is positive integer in the video, so b > 0, but it does not imply b > (q'-q)b, may I have some explanation ? thanks 

[IPear]

Why do you assume b>0? In the Euclid's division a and b can be any number (except 0 for b)

[darcash]

maybe it is obvious bc a, n, and b are all defined as ints, but should we also say a-nb exists in the nat nums to use the Well ordering principle

[debloated]

This is such a good video! Thank u very much <3

[harshsharma]

great video man, understood it soo well...thanks alott

[bibek]

beautiful explanation. Could you please explain the idea behind choosing a set for the proof (for example a set was choosen for the proof of division algorithm) i.e. in general how can I see for myself that there underlies a set and work with the set to get a proof?

[andy]

Hey, How where you able to get q-(q+1)b>=0 from a-qb-b

[nicholascousar]

I thought the Well Ordering Principle only works on sets of positive integers? Is the W.O.P. if a set contains 0 as an element?

[TuananhNguyen-klud]

Thank you for great video!
Though I have some question in the existence proof namely the part that shows S is nonempty.

One question that raised in my mind was if 0 was chosen arbitary in this line "If a >= 0, then a-0*b = a in S".

For instance if I choose 2a s.t. a - 2a*b = a(1-2b) and since b > 0 and a >= 0, then a(1-2b) < 0, which is not in S. Does it mean there are some numbers for, "n" in this case, that satisfy the condition a-bn >= 0?

A second question is how one can show that a set S is nonempty. Is it enough to somehow show that there exists positive integer values, to say that the S is nonempty?

Best regards

[ankurc]

so hard...finally understood watching over and over book is this book from/which book are you following? Can you please explain the proof in Gallian's book?