Thank you for opening with what q and r are and how you get them. A good few articles I've read don't actually say what they are, which is annoying, because for a number-phobe like myself, a more granular introduction is needed quite often. For me, just looking at the equation does not intuitively tell me that q and r are generated by dividing a and b
Hi, I'm afraid you have so many views no one would answer my question. But still. I don't understand how you can deduce that d | a -bq from d | a, d | b. Can someone explain me the intermediate steps ?
In the previous "Divisibility Basic" part, there is a propositon that " If a|b and a|c, then for any x and y as integers, there is a|bx+cy". So according to this, we have d|a and d|b, then d|ax+by where x = 1, y = -q1.
if d|a and d|b then we can write this as a = dx and b = dy (all integers). Any linear combination like pa + qb (p and q integers, again) can be written as dxa + dyb which you can factorize to d(xa + yb) which of course would be a multiple of d, the thing we initially sought to prove.
Was it a typo at 5:25? You wrote: d | b - r1 * q1 implies d | r2 I think it should have been: d | b - r1*q2 implies d | r2 Since equation 2 is: b = r1*q2 + r2
Does d | r_(n-1) imply (r_(n-1)) / d = 1 and that d = r_(n-1) ? Read: Does the last statement that d is a divisor of the last remainder imply that the remainder divided by d is equal to 1, and does that mean that d is equal to the last remainder?
Here we are using the definition of the gcd. We start by showing that r_{n-1} is a common division of a and b then suppose we have another common divisor of a and b and show that must divide r_{n-1}. This is precisely the definition of gcd(a,b). That d in the proof is only a divisor of the gcd, it may not be the gcd itself.
@@xRabidz I hope you see this comment :P As it drives me nuts :S we know that r__(n-1) is some common divisor, we do not know by the proof that it is the greatest one it may not be. So we take some divisor d, it may be the greatest but it also may not be the greatest, if we would take a d that is not the greatest one and r_(n-1) may not be the greatest one we are left with a d equal to r_(n-1), how does this proof that r_(n-1) is the greatest one ...
@@mateuszpachulski6211r_(n-1) MUST be the greatest, we are not trying to prove with contradiction here. Basically gcd(a,b) is defined that ANY divisor d of a and b must divide the gcd. Think about it, any common factors of 30 and 40 must divide 10.
rn-2 is not a divisor of rn-3, because rn-3/ rn-2 have a rest ≠ 0. I mean an example is 12 = rn-3 ,8 = rn-2 and 4 = rn-1. There you see 12/8 = 1*8 + 4 = 1,5. Not a divisor.
r1 < b otherwise the choice for q1 was wrong. r2 < r1 otherwise the choice for q2 was wrong. and so on and so forth. this is a consequence of how remainder upon division is defined.
Why can't you prove this shit works by using real world things like a field or something useful and meaningful? Why does it have to be bulk lines of gibberish simbols?
I used to watch you for fun, now you're also helping me with my degree in maths :D Thank you!
Professor Penn, thank you for a classic proof on the Euclidean Algorithm. These are historic topics in mathematics.
The way the last pos remainder percolates up. I appreciate finally explaining why it works, not just that it works.
Wow! Amazing! I actually understood this (after a lot of effort). Always love the eureka moments I get when learning about a new proof. Thank you!
Just found this channel and I'm loving the content so far! Thanks a lot
Do you know other channel like this, I want to learn more math
The last part is because d
If I am not mistaken, that's because since the sequence r1, r2, ... , r_n-1 is decreasing and that d | r_n-1 implies d
Well organized.
Thanks alot!
Thanks!
Euclidean? More like Eu-clear-ian, because now I understand; thank you so much for explaining!
Great job punmaster, you’ve successfully ruined my day😂
@@MonkeyAssassin-qi8gw Then my work here is done 👍
On the flip side, if you keep listening to painful puns, eventually you’ll become numb(er)…
@@PunmasterSTP you’re ruthless
@@MonkeyAssassin-qi8gw I once told someone something ridiculous, and they said "Euclid-en' me!"
Thank you for opening with what q and r are and how you get them.
A good few articles I've read don't actually say what they are, which is annoying, because for a number-phobe like myself, a more granular introduction is needed quite often.
For me, just looking at the equation does not intuitively tell me that q and r are generated by dividing a and b
Hi, I'm afraid you have so many views no one would answer my question. But still.
I don't understand how you can deduce that d | a -bq from d | a, d | b. Can someone explain me the intermediate steps ?
In the previous "Divisibility Basic" part, there is a propositon that " If a|b and a|c, then for any x and y as integers, there is a|bx+cy". So according to this, we have d|a and d|b, then d|ax+by where x = 1, y = -q1.
@@bingqingwang850 okay thank you very much !!!
if d|a and d|b then we can write this as a = dx and b = dy (all integers). Any linear combination like pa + qb (p and q integers, again) can be written as dxa + dyb which you can factorize to d(xa + yb) which of course would be a multiple of d, the thing we initially sought to prove.
@@mominahmed7-044 thank you very much
pausing the video to tell you that your outfit is fire as hell
Awww, i miss the sound of writing on chalk board
How cutely u just proved it and i didn't even realised that I understood. Great teacher. Thankyou so much.
Was it a typo at 5:25?
You wrote:
d | b - r1 * q1 implies d | r2
I think it should have been:
d | b - r1*q2 implies d | r2
Since equation 2 is:
b = r1*q2 + r2
Yes it is a typo
I don't know if this was intentional but the outfit and the background really match each other (ninja-like) :)
great proof, very clearly shown 10/10
Thanks for confirming how dumb I am 🙂
at 5:41 shouldn't it be d divides b-(r1q2)
Yes I think so but either way the point is clear I guess
Is this a proof by induction?
how to prove {r1,r2,r3,.....} is decreasing?I want to know
It comes from the original definition for division -
a | b => a = bq + r and 0
Hi can someone pls explain that if dIrn-1 how is it the gcd(a,b)?
@Michael Penn How do you prove that the last sequence in the division has a remainder of zero?
that's because if the remained is not zero, then the sequence will keep going on
had the same question
Does d | r_(n-1) imply (r_(n-1)) / d = 1 and that d = r_(n-1) ?
Read: Does the last statement that d is a divisor of the last remainder imply that the remainder divided by d is equal to 1, and does that mean that d is equal to the last remainder?
Here we are using the definition of the gcd. We start by showing that r_{n-1} is a common division of a and b then suppose we have another common divisor of a and b and show that must divide r_{n-1}. This is precisely the definition of gcd(a,b). That d in the proof is only a divisor of the gcd, it may not be the gcd itself.
d is assumed to be ANY common divisor of a and b, so if d | r_(n-1) then that means d
@@xRabidz I hope you see this comment :P As it drives me nuts :S we know that r__(n-1) is some common divisor, we do not know by the proof that it is the greatest one it may not be. So we take some divisor d, it may be the greatest but it also may not be the greatest, if we would take a d that is not the greatest one and r_(n-1) may not be the greatest one we are left with a d equal to r_(n-1), how does this proof that r_(n-1) is the greatest one ...
@@mateuszpachulski6211r_(n-1) MUST be the greatest, we are not trying to prove with contradiction here. Basically gcd(a,b) is defined that ANY divisor d of a and b must divide the gcd. Think about it, any common factors of 30 and 40 must divide 10.
thanks helped alot@@xRabidz
well organized video
How can we tell the sequence of r1, r2, r3 is decreasing?
By the division algorithm, a = bq + r where r < b because if it is great than or equal, it gets absorbed into q. So each r(n) < r(n-1)
what if d=1?
Then there would be no purpose in proving😅,we assume that d does not equal one as there would be no point.
Shouldnt we prove that r1 and all other r don't divide a and b
3:08 how to rn-1 divide rn-2 explain
Because we can write r_{n-2} = r_{n-1}*q_{n}, which is equivalent to saying r_{n-1}|r_{n-2} (by divisibility definition: a=bn then a|n)
@@rayzewis3361 but r_{n-2} = r_{n-1}*q_{n} + r_{n} sir you can use it not this r_{n-2} = r_{n-1}*q_{n}
yea I get this and its great and all but WHERE IS THE "And thats a good place to stop"
Thanks for a great video♥️♥️♥️
Nice one.
if d/rn-1 then d should be the gcd of a & b
It's greatest common divisor, emphasis on greatest.
When did Mark Zuckerberg start teaching Mathematics.....Lmao🤣🤣🤣
wait so how is rn-1 a divisor of rn-3 if rn-2 isnt a divisor of rn-3?
rn-2 is not a divisor of rn-3, because rn-3/ rn-2 have a rest ≠ 0. I mean an example is 12 = rn-3 ,8 = rn-2 and 4 = rn-1. There you see 12/8 = 1*8 + 4 = 1,5. Not a divisor.
We know, r_{n-1} | r_{n-2}, hence q_{n-2} * r_{n-2} + r_{n-1} | r_{n-3}.
Really a very good one easy to understand
شبه راكيتيتش
How do you prove that the sequence r1,r2,r3...rn decreases
r1 < b otherwise the choice for q1 was wrong.
r2 < r1 otherwise the choice for q2 was wrong.
and so on and so forth.
this is a consequence of how remainder upon division is defined.
Vow!!!!
Take a rest buddy, you seem pretty tired
Why can't you prove this shit works by using real world things like a field or something useful and meaningful? Why does it have to be bulk lines of gibberish simbols?
Huh can you clarify what you mean or give an example?
at 5:41 shouldn't it be d divides b-(r1q2)