$25x+9y=2014$ where $x,y\in\mathbb{Z}^+$ what is $\min(x+y)$?

Question

Assume $x,y\in\mathbb{Z}^+$ and $25x+9y=2014$. What is the minimum value of $x+y$ ?

To solve this problem I noticed that we are looking for large values of $x$ since it has coefficient $25$ so I started from $x=80,79,78,\ldots$ After trying these values I found out $x=73$ works and $y$ should be $21$. Hence $\min(x+y)=94$.

But is it possible to solve this problem without try and error? From $25x+9y=2014$ we can write $25\vert2014-9y\quad$ or $\quad9\vert 2014-25x$. But I don't know how to continue.

Answer 1

The system

$$25x \equiv 2014 \mod9 \equiv 6 \mod 9 $$

$$9y \equiv 2014 \mod25 \equiv 14 \mod 25$$

has a unique solution modulo $225$ as $(25,9)=1$. Now observe that

$$25(4) \equiv 1 \mod 9$$

$$9(14) \equiv 1 \mod 25$$

Thus

$$25(6) \equiv 6 \mod 9$$

$$9(21) \equiv 14 \mod 25$$

when we multiply both sides of each equation by $2014$.

Now a solution to the above system is $(x,y) = (73,21)$ thus all solutions are of the form $(73+9t, 21 -25t)$ where $t \in \mathbb{Z}$ if $(x,y) \in (\mathbb{Z}^{+})^2$ then $-8\leq t \leq 0$. The sum $x+y$ is $94-16t$ which is minimized at $t =0$. Thus the minimum is $94$.

Answer 2

We can write the original equation as follows:

$$\begin{align}y&=\frac{2014-25x}{9}\\ &=\frac{2007+7-18x-7x}{9}\\ &=223-2x-\frac{7(x-1)}{9}≥1\end{align}$$

Then, we get $$\begin{align}&x-1=9m,\thinspace 1≤x≤80,\thinspace x\in\mathbb Z^{+}\\ \implies &x=9m+1,\thinspace 1≤x≤80,\thinspace x\in\mathbb Z^{+}\\ \implies &x=9m+1,\thinspace 0≤m≤8,\thinspace m\in\mathbb Z_{≥0}^{+}\\ \implies &y=223-2(9m+1)-7m\\ &\thinspace\thinspace\thinspace=-25m+221,\thinspace m\in\mathbb Z_{≥0}^{+}\end{align}$$

Finally, we conclude that

$$\begin{align}\implies &x+y=9m+1-25m+221,\\ &\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace \thinspace\thinspace\thinspace=222-16m,\thinspace m\in\mathbb Z_{≥0}^{+}\\ \implies &\min\left\{x+y\right\}=222-16\times 8\\ &\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace \thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace=94.\end{align}$$