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.