# 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$$\$