Solving a Extended Euclidean Algorithm related problem Alex has some (say, n) marbles (small glass balls) and he has going to buy some boxes to store them. The boxes are of two types:
Type 1: each box costs c1 Taka and can hold exactly n1 marbles
Type 2: each box costs c2 Taka and can hold exactly n2 marbles
He wants each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them. Since he finds it difficult to figure out how to distribute his marbles among the boxes he seeks his friends' help.It is worthy of mention that the value of n,c1,n1,c2 and n2 are given.
His one friend solved this problem using extended euclidian algorithm and found out two values everytime .Thus his result for the input
1.n=43,c1=1,n1=3,c2=2,n2=4 the result will be 13 1
2.n=40,c1=5,n1=9,c2=5,n2=12,the result will be "no valid values".
Though I understand extended euclidian algorithm I can not catch how he solved this problem.Can anyone tell me how his friend sovled it using extended euclidian algorithm.Since I'm a novice learner of extended euclidian algorithm I need better explanation.
 A: The following does not answer absolutely your question, but I think that it may help.


Lemma: Let $a$ and $b$ be coprime integers greater than $1$.
    
    
*
    
*The equation $ax+by=n$ has nonnegative integer solution for $n\geq ab-a-b+1$
    
*The equation $ax+by=ab-a-b$ has no nonnegative integer solution.
    
  
Proof: Suppose that $a>b$. First, note that $n-(b-1)a\geq ab-a-b+1-ab+a=1-b$ 
The set $\{n, n-a, n-2a\ldots, n-(b-1)a\}$ has $b$ elements that are
  pairwise different mod $b$. Then, there is one of them, say $n-ax$,
  that is a multiple of $b$. Then we can write that $ax+by=n$, but we
  have to prove that $y$ is nonnegative. It suffices to show that
  $n-ax\geq 0$.
If $x<b-1$ then 
$$n-ax\geq n-a(b-2)\geq ab-a-b+1-ab+2a=a-b+1\geq 0$$
If $x=b-1$ then $n-ab+a$ is a multiple of $b$, that is, $n+a$ is also
  a multiple of $b$. But $n+a\geq ab-b+1$ and the next multiple of $b$
  is $ab$, so $n+a\geq ab$, that is $n\geq ab-a$. Then
$$n-ax=n-a(b-1)\geq ab-a-ab+a\geq 0$$
This proves 1.
To prove that $ax+by=ab-a-b$ has no nonnegative solution, just note
  that $x=b-1$, $y=-1$ is an integer solution. Other solutions of this
  diophantine equation are given by $$x=b-1+kb, y=-1-ka$$ where $k$ is
  an integer. But if $x\geq 0$ then $b-1+kb\geq 0$ or $k\geq\frac1b-1$,
  that is, $k\geq 0$ and $y\leq-1$. This proves that no solution has
  both values nonnegative, as stated in $2$.

