In this video, we're going to show how to solve Diophantine equations using the Euclid's algorithm for computing the greatest common divisor. The essence of our approach is the following theorem. Given three integers, a, b and c, where not both of a and b are equal to zero. Consider the following Diophantine equation, ax + by = c. The theorem states that this equation has a solution if and only if the greatest common divisor of a and b divides c. Okay, so this is the necessary and sufficient condition for this Diophantine equations to have integer solutions. Okay, let's prove it. So denote by d is the greatest common divisor of a and the b, and assume that our equation has an integer solution. So since d divides a and b and it is actually the greatest common divisor of a and b, we can represent a as dp and b as dq where p and q are integers. Then, continue on to the solution xy where c = ax + by and this is equal to d(px + qy) just because a = dp and b=dq. So as we see d indeed divides c in this case, okay? Now let's prove the remaining part, assume now that d divides c, so our goal is to show that then our Diophantine equation has the solution. So, since d is a greatest common divisor of a and b, it can be represented using Euclid's, extended Euclid's algorithm, as ax plus by, okay? Then we know that c, I'm sorry, let's represent it as axy plus by bar, okay, so x bar and y bar is the certificate in the sense of the fact that d is the greatest common divisor of a and b. Now we use the fact that c is divisible by d. Let's represent that c as td and let's consider the following x and y. X = t times x bar, and y = t times y bar. So what we're going to show is that these particular x and y is a solution to our Diophantine equation. So indeed, ax + by = t times ax bar + by bar, okay? But this is equal to just t times d, which is equal to c, okay? So in this case, indeed, xy is a solution. So once again, we've just stated and proved, actually, that the necessary and sufficient condition for Diophantinequation to have a solution. And in this case, what is needed is that d divides d is the greatest common divisor of a and b divides C. Okay, so let's give an example. Consider the following Diophantine equation 10 times x plus 6 times y is equal to 14, okay? So extended, the extended Euclid's algorithm used as the following representation for the greatest common divisor of 10 and 6. So 2 is equal to 10 times minus 1 plus 6 times 2, right, so [INAUDIBLE] to just multiply this equation by 7. So 2 multiplied by 7 is equal to 14 and we can also multiply it by 7 on the right-hand side. This gives us 10 times minus 1 times 7 plus 6 times 2 times 7. So in a sense, what we have here, this is our x and this is our y, right? So if x is equal to minus 7, in this case, y is equal to 14, okay? So this gives us one solution, okay? Now let's consider another example, in this case, 391x + 299y is equal to minus 69, okay? So once again, in this case, the greater common divisor of these two coefficients is equal to 23. And using the extended Euclid's algorithm, we can represent it as the linear combination of these two numbers. So the efficient of this linear combination is minus 3 and 4. Now we can multiply this equation with minus 3. So we can multiply 23 with minus 3. This gives us minus 69, exactly what is needed. On the right-hand side, we will have what was in the previous line times minus 3, and again, what was in the previous line times minus 3. So in this case, this is our x, this is our y. So x = 9, y = minus 12, okay. So this is one particular solution, but it turns out in this case there is also another solution. X is equal to minus 4 and y is equal to 5. Again, it is very natural to ask at this point how to find all possible solutions to Diophantine equation in case there is at least one solution of course. So we're going to develop this method soon, but before doing this, let's prove the following auxiliary lemma which is also called Euclid's Lemma. So if n divides a times b and also the greatest common divisor of a and n is equal to 1, then n necessarily divides b. Okay, so this is proved as follows. Since a and n, their greatest common divisor is equal to 1, let's represent 1 as a linear combination of a and n. Assume that ax and y are the coefficients of its linear combinations. So we know that there are such integers x and y, such as ax plus ny is equal to 1. And this x and y family can be actually easily found by Euclid's algorithm, okay? So let's multiply this equation by b, what we get is axb plus nyb is equal to b. Okay, now we know that ab is divisible by n, which means that ab can be represented as km. Now let's use the previous equation. So b = axb + nyb, but now we know that axb = n xk, right, just because ab is equal to km. So what we see is that n is equal to m times xk plus yb, so indeed n divides b, right, which proves the lemma. Now let's go back to the question of how to find all solutions of a particular Diophantine equation. So I assume that we have two integers a and b, such that the greatest common divisor is equal to d. Let's also represent a as dp and b as dq, and it seems that x0, y0 is a solution of a Diophantine equation ax plus by is equal to c. So it is a solution meaning that ax0 plus by0 is equal to c. So this is just a true fact. Then the theorem states that any other solution to this particular Diophantine equation has the following form. So x in this solution is equal to x0 plus dq, where y is equal to y0 minus tp where t is any integer. So once again, what we state here is there actually two statements here. First of all is for any t by considering x0 plus tq and y0 minus tp we get a solution. And the second statement is that any other solution has the following form, okay? Let's prove both these statements. So first of all, the first one. In this case, let me recall that we have a = dp, b = dq, and we also know that x0, y0 is a solution, okay. Then consider any other solution, any other two points x and y defined by x0 plus tq and y0 minus tp. So this is our nuclear xy, xy. Okay, let's consider what happens if we compute a times this x plus b times this y. This will be equal to xa times x0, it is this term, plus by0, which is this term, plus t times aq, which is this term, multiplied by a- t x bp, okay? So this leaves us t times aq minus dp, okay, so just by the fact that x0 and y0 is equal to c, we can replace this term by c. On the other hand, we know that aq = bp, okay. This is just because a = dp and b = dq. Okay, so this is just equal to zero. Okay, so this just cancels. So this shows that any x and y of this form is a solution, okay? So what remains to be shown is that any other solution has the following form. So for this, let's just show that any to any two solutions are actually different by, they differ as follows. So to get one solution from another one, we need to add dq to x and subtract dp from y. So for this, consider such two solutions x1, y1 and x2, y2. So we know that ax1 plus bx, by1, I'm sorry, is equal to c, and the same holds for x2, y2. So this means that we can subtract one form another. So listen from the other ones. So this will leave us the following equation. A times x1 minus x2 plus b times y1 minus y2 = 0. Okay, so this our equation. Okay, so in this case, let's divide this equation by d. What we will get is the following. So a divided by d is equal to p, b divided by d is equal to q. So this is our new equation, okay? Now, what we know is that the greatest common divisor of p and q is equal to 1, okay? This allows us to conclude, since this is divisible by q and this is divisible by q, we know that this is divisible by q. On the other hand, p and q is the greatest common divisor of p and q = 1, which means that x1 minus x2 by Euclid's lemma should be divisible by q, right? So we can represent x1 minus x2 by tq. This already shows us the two x's are different by a multiple of q, right? This is actually x1 minus x2 = tq. And in this case, if we plug this tq into this equation, this will give us the difference of y1 minus y2 = tp. So exactly what we needed to prove. So this concludes the proof of this lemma as it allows us to express all solutions to the Diophantine equations over some initial single solution, okay. Let's finally show an example of applying this lemma. So once again in this case, we have three pesos times nine equals three bills of three pesos, so this is 27 plus five is equal to, I'm sorry it should be minus five is equal to 22. Okay, it should be plus five times minus one. Okay so in this case, we are solving the following Diophantine equation, 3x + 5y = 22. And we know that there is a single solution, at least one solution to this problem, expressed as follows. x0 = 9, y0 = minus 1, okay? Let me also recall that in this particular case, a is equal to three, b is equal to five and their greatest common divisor denoted by d is equal to one. So in this case, the numbers p and q are also equal to three and five. So b is just equal to a, q is equal to p just because the greatest common divider is equal to one. So that our theorem states that any other solution is expressed through our initial solution, which is as follows: 9 minus 1 as follows. It is 9 plus 5t, this is x and y is minus 1 minus 3t, okay. So this gives us the whole range of solutions. So for any integer t, this gives us a new solution, okay. Assume at the same time recal that in our case we would like x and y, we would like x to be non-negative and y to be non-positive actually, right? So in this case, this translates to the following set of inequalities. So we would like 10 plus 5t to be at least 0 and we would like minus 1 minus 3t to be at most 0, okay? So just by solving this through simple inequalities, we get, the t should be at least minus 3, okay? And since t must be an integer, it just means the t should be non-negative. So what we get in the end is that any solution x = 9 plus 5t and y = minus 1 minus 3t g gives us a valid solution to our Diophantine equation. For example, by taking t = 10, you get a solution x = 59 and y = minus 31. Which means that if you give 59 three peso bills to the cashier and the cashier returns to you 31 five peso bills and one apple, this will be a fair trade.
