TITLE: How to find a pair of solutions of Linear Diophantine equation such that you minimize this expression?
QUESTION [1 upvotes]: This is a typical Math coding Problem I encountered here Problem.
So Let me break it to you 
Suppose you have two values $a$ and $b$ and to select this  value $a$ one time it takes you $c_1$ cost and it takes $c_2$ cost to use value $b$.
You are to solve this equation for $(x,y)$  $ax$ + $by$ = $N$ where $N$ is a value given to you 
Find such $(x,y)$ that you minimize this expression $x*c_1 + y*c_2$.  or report if it is not possible to solve  
It is a clear cut Linear Diophantine equation and I can easily solve for $(x,y)$ by using Extended GCD But I don't how to do it by minimizing the given expression.
An example for this question is suppose you have $a=3$ $b=4$ and $c_1 = 1$ and $c_2=2$ and $N=43$
 $x=13$ and $y=1$ can do the trick for us  by minimizing  the given expression.

REPLY [1 votes]: Let $d>0$ be the greatest common divisor of $a$ and $b$. Fix an arbitrary solution $(x_0,y_0)$ of the equation $ax+by=N$. Let $(x,y)$ be any solution of this equation. Then $a(x-x_0)+b(y-y_0)=0$, so $d(x-x_0)|b$, that is $x=x_0+kb/d$ for some integer $k$. Conversely, for any integer $k$, $(x_0+kb/d, y_0-ka/d)$ is a solution of the equation. This solution costs $c_1(x_0+ kb/d)+c_2(y_0-ka/d)$, which is $k(c_1b-c_2a)/d$ than the cost of the solution $(x_0,y_0)$. This follows that a solution of the equation with the minimum cost is:

a solution with minimum $x_1$, when $c_1b>c_2a$,
a solution with    minimum $x_2$, when $c_1b<c_2a$,
any solution of the equation, when    $c_1b=c_2a$.
{"set_name": "stack_exchange", "score": 1, "question_id": 3959815}