Minimum of restricted linear combinations. Let $\{N_0, ... , N_m\}$ be a set of natural numbers, then the minimum $(\geq 1)$ of all their linear combinations is their GCD. Is there a way to calculate that minimum if some $N$s can only be subtracted, while others can only be added?
Also I'm wondering if there exists a name for this.
 A: Answer : As I said in a comment this number is always their gcd if there is at least one number that w're allowed to subtract and one that we can add. When we don't allow subtractions this is a well known difficult problem Frobenius problem.
Let $n\geq 2$ be an integer and $a_1,\cdots,a_n$ be a sequence of positive integers, WLOG we can assume that we are allowed only to subtract $a_1,....,a_k$ and the other ones we are only allowed to add them, hence as I said we can obtain the gcd even if we add this assumptions, and it's of course the smallest integer which can be obtained which is a combination of these integers.

Formalization of the question: we claim that for every $0<k<n$:
$$d=\gcd(a_1,\cdots,a_n)=\text{min}\left\{ \alpha_1a_1+\alpha_2a_2+\cdots+\alpha_n a_n\big /\alpha_1,...,\alpha_k \in \mathbb{Z}_{-}\, \alpha_{k+1},...,\alpha_n \in \mathbb{Z}_{+} \right\} $$
Here I'm including $0$ in both $\mathbb{Z}_{+}$ and $\mathbb{Z}_{-}$.

Proof
According to Bézout's identity one could argue directly that :
$$\text{min}\left\{ \alpha_1a_1+\alpha_2a_2+\cdots+\alpha_n a_n\big /\alpha_1,...,\alpha_k \in \mathbb{Z}_{-}\, \alpha_{k+1},...,\alpha_n \in \mathbb{Z}_{+} \right\}\geq d$$
Because we can not write an integer less than $d=\gcd(a_1,\cdots,a_n)$ as a linear combination of the integers $a_i$.
Now in order to prove the equality, we need to prove that , there are $\alpha_1,\cdots,\alpha_n$ such that
$$d= \alpha_1a_1+\alpha_2a_2+\cdots+\alpha_n a_n\big /\alpha_1,...,\alpha_k \in \mathbb{Z}_{-}\, \alpha_{k+1},...,\alpha_n \in \mathbb{Z}_{+} $$
we will prove this by induction on $k$ :

*

*Basis Step $k=1$ first there are integers $x_1, x_2, \ldots, x_n$ such that
$$d = a_1 x_1 + a_2 x_2 + \cdots + a_n x_n $$
Now we want to make $x_2,\cdots,x_n$ positive and make $x_1$ negative. to do that let's take take $\alpha= (|x_1|+\cdots+|x_n|)a_1a_2\cdots a_n$ and take:
$$\alpha_1=x_1-(n-1)\frac{\alpha}{a_1}<0\quad \quad \alpha_i=x_i+\frac{\alpha}{a_i}>0 \text{ for every } 2\leq i\leq n$$
and of course we have $d=\alpha_1a_1+\alpha_2a_2+\cdots+\alpha_n a_n$

*Induction step assume that the result is true for $k<n-1$ meaning that there exists some integers $x_1,\cdots,x_n$ such that:
$$d= x_1a_1+\cdots+a_n a_n \text{ and } x_1,\cdots,x_k\leq 0 \quad x_{k+1},\cdots,x_n \geq 0 $$
As $k<n-1$ and hence $k+1\neq n$ it suffices to replace $x_{k+1}$ by $x_{k+1}-|x_{k+1}|a_n$ and replace $x_n$ by $x_n+|x_{k+1}|a_{k+1}$ which proves the claim for $k+1$.

