0:00

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.

Â 3:15

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.

Â 9:53

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.

Â 11:15

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.

Â 12:59

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.

Â