# A problem regarding Extended Euclidean Algorithm

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.

1. A number $n$ cannot be represented as a linear combination of $n_1,n_2$ unless $(n_1,n_2) \mid n$, since all linear combinations of $n_1,n_2$ are multiples of $(n_1,n_2)$.
2. The extended Euclidean algorithm gives you values $a_1,a_2$ such that $a_1n_1+a_2n_2 = (n_1,n_2)$, and in particular $$\frac{n}{(n_1,n_2)} a_1 n_1 + \frac{n}{(n_1,n_2)} a_2 n_2 = n.$$
3. If $n = b_1 n_1 + b_2 n_2$ then all other representations are of the form $$n = \left(b_1 + \frac{n_2}{(n_1,n_2)} t \right) n_1 + \left(b_2 - \frac{n_1}{(n_1,n_2)} t \right) n_2.$$