Bézout's Identity Explained: Finding Integer Solutions via Euclid's Algorithm

[00:00:00]Okay, in this video I'm going to demonstrate one of the most useful facts in number theory. That is when you give me any two integers and let's just go ahead and call them to be a and b. We are always able to find x and y and they are also integers such that ax plus b y is equal to the greatest common divisor of a and b. I will just give you guys an example and of course I will have to start with two numbers and let's just say I want to use 132 and 126.

[00:00:31]So we have these two numbers and as I said earlier let's go ahead and find the greatest common divisor of these two numbers. So let's go ahead and find the GCD of these two.

[00:00:42]And of course you can do the good old way go away. You can just draw the factor trees and things like that.

[00:00:50]Right? Nice and cute. But we are all adults. Now let me show you guys the number theory way. This right here is called the Uklit algorithm. Not oiler Uklit. All right.

[00:01:03]Uklit algorithm. And it goes like the following. I know uh you pretty much just use what we call the long division. And the technical term for that it's technically uh division algorithm and the textbook way is kind of hard to follow in my opinion.

[00:01:20]So let me show you guys how I will just work out the computation first. So I would like to put down these two numbers right here for you guys. 432 and then 126. And I will first draw a line in between them and I'll draw like these two lines right here just like a wall. And now here's the deal. If like at the end of the day we're still trying to divide one with the other and things like that. Okay. Anyway, first we are going to ask ourself how many times does 126 goes into 432 and just work that out. You can divide whichever way. Do a scratch paper, use calculator, whatever.

[00:02:01]But three, right? Because I know if I do 3 * 126, I get 378.

[00:02:11]So from here, let's go ahead and subtract 432 minus 378, we shall get 54. So it's just like the long division organized in this way. All right. And the reason is because now I'm going to use 54 and divide into 126. How many times does 54 goes into 126? If you think about it, you get two.

[00:02:38]2 * 54 is 108. And now you subtract and you get 18. And you see it's pretty much like you go from here to here and then from here to here and you go from here to here. It's like a zigzag uh division.

[00:02:52]Kind of cool, huh? Anyway, 18 goes into 54 how many times? Well, this is so nice because 18 goes into 54 exactly three times. 3 * 54 we get I mean 3 * 18 we get exactly 54 and we are done because here we have zero. And once we have this is zero it's done. And we are always able to you know just apply as many steps as possible to reach zero because one is always a common factor of any two numbers and the worst case is that one is the greatest common divisor of those numbers. So this is always going to work and the number before the zero which is the 18 right here in your case this right here it's exactly the greatest common divisor. So in fact I know the answer right here. It's equal to 18.

[00:03:50]So this is the uclus algorithm setting up this way. I think it's a lot nicer in my opinion. Okay. Let me show you guys how the textbooks will show you. All right. Here is the deal. You still do long division and then maybe you want to do a long division on a scratch paper and then use the remainders and things like that. But let's see. Start with the bigger number which is 432.

[00:04:15]You want to write this as some number times 126 plus some other number. In another word you ask yourself 126 goes into this how many times and things like that and sometimes you have to add but we did the work already.

[00:04:33]126 goes into 432 three times with the remainder 54. So I know right here I can just put down three and then we add 54 in the end like this.

[00:04:47]Next I will use 54 and then divide into that. Right? So I'll put this down right here. 126 and then I have to ask myself this is equal to what times 54 and plus what? We did the work right here already. We know it's going to be two and then plus 18.

[00:05:07]So it's kind of cool, right? And you see this goes there. This goes there, right?

[00:05:12]So it's like that. It's like that kind of diagonal movement. Really cool. Now put down 54 right here. And you should use this right here. And this should be three. We did that. 18 goes into 54 three times. Cool, huh? And we are done.

[00:05:31]Of course, you don't need to put on the plus zero if you don't want to. This remainder right here is zero. That means the remainder prior to this step which is the 18 here. This right here is the GCD.

[00:05:45]Done. This is the usual way the textbooks present it. And we actually need to use this way. Why? Because I haven't showed you guys how to find the x and y yet. We actually have to look at this and reverse the steps in order to find um the x and y integers. And as I said, this is just one of the steps.

[00:06:05]Sometimes you may be able to just eyeball the equation and then just find out x and y inter solutions. But why?

[00:06:12]Anyway, here is the deal. I will show you guys how to actually find x and y so that we do x times this plus y * that. We end up with 18. So here is what we want. I want to have let me put down 432 * x plus 126 * y. And as I said, I will make this equal to 18 for you guys.

[00:06:40]And of course, when you have big numbers like this, it's not easy to just eyeball this and figure out x and y anymore, huh? And another thing I want to mention is that x and y can be integers, right?

[00:06:52]They can be positive or negative integers. So yeah, anyway, here we go.

[00:06:57]Start from this line because we got 18 right here. So let's go ahead and put this down. This is the 18. Okay, I will write 18 is equal to let's move this to the other side and do not multiply this out. Keep this as how they are. All right, do not multiply this out. So let me write down 126 and then minus 2 * 54.

[00:07:23]So we use this equation already. Now I will go back to this equation. I will pay attention to this 54 and I will isolate this 54 by subtract this to the other side and then I will replace that 54 expression right here. So let me show you. I will keep the 126 right here and I will still keep the minus2 right here.

[00:07:46]But I will multiply 54 as 432 and then minus 3 * 126.

[00:07:57]And once again, don't multiply this out.

[00:08:01]Let me show you why. Because we know we are smart. So don't do that. Anyway, this right here is 126 minus. Of course, now you distribute just like the good old days. Once again, do not multiply this out. Keep them as how they are. I will just write down 2 * 432 but -2 * -3 we have to multiply that out multiply the coefficient this times that give us + 6 * 126 in the end you see that this is 126 and then we also have the 432 hey that's exactly what we want isn't it all right this is so cool and of course this is like saying 1* * 126 and 1 * 126 + 6 * 126 that's 7 * 126 like just pretty much combine like term that kind of thing you just don't multiply out I think I said don't multiply it out like five times but you know anyway let me put this down because I put down 432 first so let me put this down minus 2 * 432 1 + 6 is of course + 7 * 126.

[00:09:17]Check this out. This right here, we have a number and this is precisely an integer. -2 * 432 plus 7 * 126. So one of the solution is just we take X to be this and Y to be that. Right? So let me just put you guys uh let me just give you guys one of the solutions right here. One solution is that I will just take x to be -2 and then y to be seven positive seven and this is going to work. Why? Because this times this plus this times that boom is equal to 18. Done. Right?

[00:10:06]Okay. Now if I just end the video, I know a lot of you guys are going to comment. Is this the only answer? And how in the world can we actually find all these solutions? So of course we are not done yet. This is just one of the answers and I will just say this is how we can get the answer by using the ukidian uklid algorithm or ukidians algorithm and you do it backwards like this. Um I will just call this to be x knot and y not because this is like the initial values that we got right and right here we are going to find all the solutions and let's look at this again let's put down 432 open the parenthesis and let's put down the first x value that we have namely -2 and we are going to leave a space we will see why later close the parenthesis and then add 126 open the parenthesis put on seven leave a space and we know this right here has to be equal to 18 because we did that earlier. And here is the idea. I want to generate all the solutions for you guys. And this is where the x is and this is where the y is.

[00:11:13]The idea is that maybe I need to add something right here. Huh? And when I add something here, I will have to multiply this with 432 because of the distribute. And when I do that, I will get a positive result. And wouldn't it be nice if I can just subtract the same result right here? But in that case, I will have to minus a number inside here and multiply with 126 and match with that. So the deal is I would need to find a multiple of this and that right so that in the end when I distribute when I distribute they are the same number but opposite sign that it's the strategy and when we are talking about multiple why don't we look for the lowest common multiple and to do so let's look back to here okay so we have 432 earlier and we Now the greatest common divisor is 18 for this two. So I can look at this and break this down as 18 and you can just do this divide by 18 which is 24. So in other word this is equal to 18 * 24. On the other hand 126 I can look at this as 18 times you can work that out you get seven. And based on this I can tell you this is how you can find the lowest common multiple of 432 and 126.

[00:12:37]Notice that 24 and seven they are relatively prime because we just put all the divisor the common divisor to the 18 right here already. Right? When we have this situation what we can do is just put down the greatest common divisor which is 18 and put it down one time and then put down this and put down that multiply there. That's it. This is going to be the lowest common multiple of these two numbers. And if you would like to know how big this number is, this is just 3,24.

[00:13:10]But let's look at the factor form in this way first. Okay, refer back to this. Now here we have 432.

[00:13:19]I want to multiply by something right here. So I end up with 300 3,24, right? Well, 432 is 18 * 24. All I need to do is just multiply by 7. So right here let me multiply by positive7. And when you distribute this part this times that you do get this right here namely 3,24.

[00:13:46]All right.

[00:13:48]And then in order to kill this number because now we have 3,24 more. I will have to minus and this times what will give us 3,24?

[00:13:59]Well, 126 is 18 * 7, which is this and that, that means I need a 24. So, I just have to minus 24 right here. So, that when I do this times that, I will get minus 3,24.

[00:14:15]All right? So, that's the cool part. And of course, as I said, when you do this times that and this times that, the red part right here, they will still combine to be 18. got this and that they cancel each other out to be zero. But let me still work this out for you guys though.

[00:14:31]This times that is 80064 and this was a positive blue number and then this times that is positive and this times that is 84882 like this. And if you verify this plus that we do get the 18, right? So that's cool. So now when we have this you see the inside is just -2 + 7 and that's exactly just five. On the other hand 7 minus 24 we get -17.

[00:15:10]So another pair for the solution is five and 17. Really cool right? And can we do better because we want to find all these solutions. Yes, we can because when you have plus seven, why don't we just do plus 14 and just double this? In the meantime, you just double that and they will still be the same number but opposite sign. So, I can multiply this by two. I can multiply this by whatever integer I want. And since this is plus, maybe I want to have a minus first.

[00:15:42]That's okay, too. But, as I said, let's just multiply this by an integer. And let me just say m right here. and do the same thing here. So that when you do this times that, you get 3,24 m and then minus 324 m. They still cancel out to be zero. This and that still give you the happy 18 that we want, right?

[00:16:06]Okay. And in the end, I will just write this down legitimately for you guys. For the x, I will just start with -2.

[00:16:15]And then we just add 7 m. And then for the y, it has to be in the form of 7 minus 24 m. And this is what we do. I'll just say for some m in the set of integers. But anyway, this right here is how you can present all the X and Y to satisfy this. Anyway, hopefully you guys like this video and once again, if you guys would like to know more about number, be sure you guys check out Max's videos and he has a lot of great stuff as well. And also, if you're new to my channel, please subscribe. I like to make math videos for you guys. And as always, this is it.

[00:17:03]And also if you have any questions about some math problem or math concept, I would love to think about to make a video and share this math this math concept with you. Why I'm interested in this math channel? It really helps when I'm trying to explain some math concept to others people. I'm really starting to understand if I understand the concept or not. So thank you for watching and bye-bye.