4 ms·
What's the technique used by this teacher to solve ax+by=GCD(a,b)?
https://www.youtube.com/watch?v=di3OXhHMZmI
It starts at 6:16
I can't share image here, so take this link for image.
https://mathforums.com/proxy.php?image=https%3A%2F%2Flh4.googleusercontent.com%2FvXyHA4zg8R-jOWdHVkm7Q8IPcevrsZZSGiKMx08gNnBoCRtY_ElYpeUHKoSKYjpEn7-Y7H_3UkKsqeaHx58g7-RiRdsbNA79KXY6XTbO_9XvqKKZSAidxFT5FhXIqcLz02P8DtBbZJSRxixIFEj0ESs&hash=83f9286e92f414517d400a4793be7756
It's the part where he's pointing his hand in this picture. I didn't get it although it's pretty mechanical, so I'd like to learn that technique as this is really useful in RSA algorithm(rather than having to memorize some values). I've been searching for a method like that since I saw this problem(been months) but could not find a technique like that. And it was always about just do it rather having any mechanical method like this one. So, I want to learn this.
Or, if you have any other simple methods to solve this equation, please tell me
Do you've any forums recommendations for getting help like this? I don't want to ask in stackexchange at first as they are pain in the ass always removing.
- aaplok 4y agoThis is the extended Euclidean algorithm, to find Bézout's coefficients. Column `d` contains the iterates of the classical Euclidean algorithm. Every row is the remainder of the two preceding rows. Eventually you get to the gcd. Then, every number in `d` can be written as `ax+dy`. For the first two rows it's obvious: in the first row he sets `d=x`, so it easily comes that `a=1` and `b=0`. Similarly for the second row, where `d=y` then `a=0` and `b=1`. Then from there it's basic algebra: if `a[i-2]x + b[i-2]y=d[i -2]` and `a[i-1]x + b[i-1]y=d[i -1]` you can easily prove that `a[i]x + b[i]y=d[i]`.