Our second example, our second application of the Euclid's
algorithm is solving Diophantine equations.
These are polynomial equations in integer variables,
named after the ancient Greek mathematician, Diophantus.
Okay, so to introduce these equations, imagine the following situation.
Imagine that you are at Cuba and you would like to purchase an apple.
The price of an apple is 22 pesos.
So the problem is that you only have 3-peso bills.
And the cashier, in turn, only has 5-peso bills.
So what you would like to do is to give the cashier some number of 3-peso bills.
And in return you would like the cashier to give you 5-peso
bills plus an apple whose price is 22 pesos.
So in a sense what you would like to do is to solve
the following Diophantine equation.
3x = 22 + 5y, where x is the number of bills
that you're going to give to the cashier.
And y is the number of 5-peso bills that the cashier is going to give you.
So in particular, for this equation,
there is a solution where x is equal to 9 and y is equal to 1.
So let's check that indeed it holds.
So this is 3 times 9, so this is 27.
This is 5 times 1, this is just 5.
And the price of the apple is 22, so indeed 27 = 5 + 22, right?
And it turns out that there is another solution.
So for example, you can use x = 14 and y = 4.
Let's check, once again, on the left-hand side we have 42,
right here we have 5 times 4 which is 20 plus the price of an apple which is 22.
So again, this is a solution.
So now imagine a different story.
So you have a receipt with two blots on it.
So what you can see from this receipt is that this is for some number of lamps.
The price of each lamp is $49.36 cents, I'm sorry.
What you also see is that the total price is some number ending with 7.29 and
you would like to recover all the missing information.
So the point is that in this case, again,
you are going to solve some Diophantine equation.
Let's try to come up with this equation.
So first of all, you know that there is some number of lamps denoted by x.
You know that the price of each lamp is 4,936 cents.
Okay, then let's denote by y, the number which is missing here.
So just by looking at this,
in this part of the receipt you conclude that y consists of three digits.
So y is some integer from 100 to 999.
So y is at least 100, and y is smaller than 1,000.
And you know that, in this case, the total,
in cents, is represented as follows.
It is 1,000 times y + 728.
So what you are going to solve in this case is the following
Diophantine equation.
So 4,936x = 100y + 728 where, again, x and
y are integers and we also have an additional
restriction that y has to be the small digit.
And it turns out that, in this case, the solution for
this problem, for this equation can be uniquely recovered.
So you can easily recover all the missing information here,
which gives you the following solution.
Now let's continue two more examples.
So for example, consider the following Diophantine
equation, 187x + 55y = 121.
So one solution, in this case, is given by x equal to 3 and y equal to minus 8.
So you can easily check that it is indeed a solution.
It turns out, again,
that there is another solution where x is equal to minus 2 and y is equal to 9.
In fact, there are infinitely many solutions for
this particular Diophantine equation.
Now let's consider one more Diophantine equation,
namely 187x + 55y = 45.
It turns out that for this particular equation, there are no solutions at all.
And then at this point, it is very natural to ask, why is that?
So when a Diophantine equation has a solution.
And this is exactly the subject of our next video.