Linear diophantine equation

A diophantine equation is an equation of the type: $a \cdot x + b \cdot y = c$ where $a$ , $b$ and $c$ are three integers, and it is necessary that the solutions $x$ and $y$ are also integers.

The diophantine equations do not always have a solution. In fact, a diophantine equation only has a solution if the independent term (in our case, $c$ ) is divisible by the highest common factor of $a$ and $b$ .

In this case infinite solutions exist, which are given by: $\begin{array}{rcl} x & = & \frac{c}{h c f (a, b)} s_{n} + \frac{b}{h c f (a, b)} k \\ y & = & \frac{c}{h c f (a, b)} t_{n} + \frac{a}{h c f (a, b)} k \end{array}$ where $s_{n}$ and $t_{n}$ are the coefficients of the equality: $h c f (a, b) = a \cdot s_{n} + b \cdot t_{n}$ found by means of the Euclides algorithm, and $k$ is any integer.

An interesting application of the diophantine equations is that they allow us to solve problems in everyday life. For example,

Example

Let's suppose that a gentleman is going to buy a book that costs $23$ €. Nevertheless, when he is going to pay he realizes that he only has coins of $2$ €. Moreover, the bookseller only has $5$ € notes. Can he pay the exact price of the book?

Well, this is solved by the following diophantine equation: $2 \cdot x - 5 \cdot y = 23$

The $x$ represents how many coins of $2$ euros the gentleman has to give to the bookseller, and the $y$ how many $5$ € notes the bookseller has to retur to him as change, so that the gentleman is paying exactly $23$ €.

It is clear that the $x$ and the $y$ have to be integer, since the gentleman cannot give, for example, $6$ coins and a half, or the bookseller cannot return him $1.33$ notes.

Well, as we have already seen, the diophantine equation has its solution as $h c f (2, 5) = 1$ , which divides $23$ . Besides a solution by means of the previous method, is $x = 14$ and $y =$ 1.

Namely the gentleman has to give to the bookseller $14$ coins of $2$ €, and he has to return him one $5$ € note: $2 \cdot 14 - 5 \cdot 1 = 23$