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:$$\displaystyle \begin{array}{rcl} x & = & \frac{c}{hcf(a,b)} s_n+\frac{b}{hcf(a,b)}k \\ y &=& \frac{c}{hcf(a,b)} t_n+\frac{a}{hcf(a,b)}k\end{array}$$where $s_n$ and $t_n$ are the coefficients of the equality:$$hcf(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,

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 $hcf (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$$