@3:30 ... I think this should be ... Since S is a nonempty set of positive integers, it has a minimum element d=ax+by by the *Well-ordering principle* rather than by the Archimedian principle.
This guy does a good job talking through proofs. And from the videos I've watched, he subtlety gives motivation for definitions and theories. Which I think is a sizable pitfall in teaching modern mathematics.
@@khbye2411 hello, so in math sometimes we are presented with theories that seem to have no motivation. Often it’s the case, the more math we learn the clearer the reason for those theories. Hence motivation to declare an idea a theorem
I’m a bit confused about having c|d implies d=gcd(a,b). Is it because we can apply this reasoning of c|d for any common divisor of a and b and the smallest number d for which this holds is by definition the gcd(a,b)?
Hey! I know I'm slightly late, but since d divides a and b, and c also does that, and c divides d, that means d>=c (d,c€N). And since we didn't make any assumptions about c other than its a natural no that divides a and b, and yet, d is greater or equal to it, hence, its the greatest common divisor. I hope this was clear
You can illustrate this on a spreadsheet, iteratively subtracting the small number from the larger. Eventually one of them is zero, and the other must be the GCD.
Think back to long division -- we keep going until the remainder is less than the divisor, otherwise we really haven't finished our division. For example, we don't say 53 divided by 4 is 10 with a remainder of 13, we say it is 13 with a remainder of 1. That is, we don't say 53 = 4(10) + 12, we say 53 = 4(13) + 1, where the r lies between 0 and 4.
Alternatively, you can use the Euclidean Algorthm to compute the gcd(a, b) and then reverse all the steps to discover that ax + by = gcd(a, b), but this is less elegant and more tedious.
Can someone tell me why ax+by greater than 0 is a subset of the natural numbers. It seems to me that the expression would encompass all the natural numbers: 1, 2, 3, ... What am I not seeing?
When he says 'subset of N', he does not necessarily mean that it is a strict/proper subset of N (that is, it *could* be N itself); however, it is yet unclear as to whether it is exactly N or just some part of N, noting that if it were always precisely N, then the proof would follow trivially (as gcd(a,b) is in N by definition).
Consider a = 2, b = 4. Clearly - as we've defined that x,y are integers - any solution to our given form can only be an even integer, whereby we have at least one counterexample to S always being equivalent to N.
Now, West aggressively started GCD as saying as Euclidean Algorithm. Thank u that you have not said that. Bezout' s identity is also named as Extended E Algorithm.
Suppose a = 17 and d = 6, so d does not divide a, as 6 doesn't divide 17. But, you can write 17 = 6(2) + 5. Here a = 17, d = 6, r = 5. So, a = d(q) + r. Notice that r can't be 6, because if it were, then 17 = 6(2) + 6 = 6(3) and then 6 would divide 17, which it obviously doesn't. Similarly, r can't be zero, because if it could be, than we could find an integer q such that 17 = 6(q) + 0 = 6q, and clearly there is no integer q that satisfies 17 = 6q. Putting it all together we have a = d(q) + r, where 0
The GCD is used for a variety of applications in number theory, particularly in modular arithmetic and thus encryption algorithms such as RSA. It is also used for simpler applications, such as simplifying fractions.
Wow, not only was that a completely different proof than the ones i have seen before, it was much more intuitive, thank you.
Thanks, I just filmed and edited a video of this identity for polynomials. It should be up in a few days.
Michael Penn thanx a lot for the proof
Same thoughts here. Amazing proof!
Best mathematicians combine intution without loss in generality.
@3:30 ... I think this should be ... Since S is a nonempty set of positive integers, it has a minimum element d=ax+by by the *Well-ordering principle* rather than by the Archimedian principle.
yup same thought and its correct
Greatest Common Divisor? More like Greatest, Coolest Description! Thanks so much for making all of these wonderful videos, and then sharing them.
first time i've seen such an approach to this identity. amazing work! thank you from Lebanon
I just started the book by Joseph Gallian and got stuck on this proof. This video is really helpful. Thanks a lot.
Excelent proof. Huge thanks from Brazil!
Professor M. Penn ,thank you for a classic topic and selection of The GCD as a linear combination.
I'm working on Richard Hammack's book of proof and this video is a great compliment.
Sir your explanations just make fall in love
hey sir can u say me how did the q come at 6:20 when using the division algorithm?
That proof was so intellectually satisfying!
Thank you for the hard work
Why do we get the contradiction for r
Is Michael on the bridge of the USS Enterprise?
This guy does a good job talking through proofs. And from the videos I've watched, he subtlety gives motivation for definitions and theories. Which I think is a sizable pitfall in teaching modern mathematics.
hello may I know what you mean by gives motivation for definitions and theories?
@@khbye2411 hello, so in math sometimes we are presented with theories that seem to have no motivation. Often it’s the case, the more math we learn the clearer the reason for those theories. Hence motivation to declare an idea a theorem
I’m a bit confused about having c|d implies d=gcd(a,b).
Is it because we can apply this reasoning of c|d for any common divisor of a and b and the smallest number d for which this holds is by definition the gcd(a,b)?
Hey! I know I'm slightly late, but since d divides a and b, and c also does that, and c divides d, that means d>=c (d,c€N). And since we didn't make any assumptions about c other than its a natural no that divides a and b, and yet, d is greater or equal to it, hence, its the greatest common divisor.
I hope this was clear
You can illustrate this on a spreadsheet, iteratively subtracting the small number from the larger. Eventually one of them is zero, and the other must be the GCD.
Congratulations for 100k familys of mathematics.
This is an ideal presentation.
In the CLRS Introduction to algorithms there is recursive algorithm for this
Hands down best explanation
why did you prove that d divides a through all that? you claimed that d is the gcd(a,b) so by definition d has to divide a right?
Thanks for all
Wow, I remember seeing this proof in my math circle and not really understanding anything.
Great, thx a lot from Turkey.
from Morocco all respects and thanks
Finally found a proof huhh all the other TH-camrs are just giving examples
Could someone elaborate why r is less than d?
Think back to long division -- we keep going until the remainder is less than the divisor, otherwise we really haven't finished our division. For example, we don't say 53 divided by 4 is 10 with a remainder of 13, we say it is 13 with a remainder of 1. That is, we don't say 53 = 4(10) + 12, we say 53 = 4(13) + 1, where the r lies between 0 and 4.
Alternatively, you can use the Euclidean Algorthm to compute the gcd(a, b) and then reverse all the steps to discover that ax + by = gcd(a, b), but this is less elegant and more tedious.
i don't understand. we want to proof a.xo + b.yo=d but again we use a.xo + b.yo =d why ???
thanks from canada:)
Amazing explanation!
Can someone tell me why ax+by greater than 0 is a subset of the natural numbers. It seems to me that the expression would encompass all the natural numbers: 1, 2, 3, ... What am I not seeing?
When he says 'subset of N', he does not necessarily mean that it is a strict/proper subset of N (that is, it *could* be N itself); however, it is yet unclear as to whether it is exactly N or just some part of N, noting that if it were always precisely N, then the proof would follow trivially (as gcd(a,b) is in N by definition).
Consider a = 2, b = 4. Clearly - as we've defined that x,y are integers - any solution to our given form can only be an even integer, whereby we have at least one counterexample to S always being equivalent to N.
thank you soo much ! from india
great explaination
Now, West aggressively started GCD as saying as Euclidean Algorithm.
Thank u that you have not said that. Bezout' s identity is also named as Extended E Algorithm.
No one cares
Thank you Sir ☺
thanks, very clear
Why r is less than d ?
Suppose a = 17 and d = 6, so d does not divide a, as 6 doesn't divide 17.
But, you can write 17 = 6(2) + 5. Here a = 17, d = 6, r = 5. So, a = d(q) + r.
Notice that r can't be 6, because if it were, then 17 = 6(2) + 6 = 6(3) and then 6 would divide 17, which it obviously doesn't.
Similarly, r can't be zero, because if it could be, than we could find an integer q such that 17 = 6(q) + 0 = 6q, and clearly there is no integer q that satisfies 17 = 6q.
Putting it all together we have a = d(q) + r, where 0
@@davidbrisbane7206 as a sidenote, since the equation a = d.q + r is symmetric with respect to q, we can also write 0
Thank you
let:
1/(a-b)(a+b)=A/(a+b)+B/(a-b)
and form it
■A(a-b)+B(a+b)=1
■a(B+A)+b(B-A)=1
Here are two cases of a Bezout's Lemma.
say some thing about that.
Thanks from india .
Thanks
i don’t get it
good.
I’m still watching….until the Good Place to Stop…?!?
It’s the Well-Ordering Principle, not the Archemedian Principle 😃
for what we found gcd,any use
Never ask a mathematician for applications
@@ranjitsarkar3126 it’s all for fun and glory :)
The GCD is used for a variety of applications in number theory, particularly in modular arithmetic and thus encryption algorithms such as RSA. It is also used for simpler applications, such as simplifying fractions.
Great content!
estas re mamado amigo
dafuq just happened
Lol Bezout's Identity
Very clever 👏👏.
The hysterical substance microcephaly prefer because advertisement physically risk amid a knowledgeable teacher. normal, tacky peripheral