Does the Frobenius coin problem require the denominations to be pairwise relatively prime?

In the Frobenius Coin problem (or Chicken McNugget theorem) for $n>2$, do the numbers have to be pairwise relatively prime, or just relatively prime in totality?

Solution 1:

They$\let\geq\geqslant\let\leq\leqslant$ need not be pairwise relatively prime. The reason why is essentially that Bézout's theorem works fine when we are only given that $\gcd(a_1,\ldots,a_n)=1$. Of course, it does not immediately follow that we can take the Bézout coefficients positive for sufficiently large numbers. Here's a quick way to see why:

Suppose we want to write $m\in\mathbb N$ as $x_1a_1+\cdots+x_na_n$ with $x_1,\ldots,x_n\geq0$. Bézout already gives us such $x_1,\ldots,x_n\in\mathbb Z$, but they can be negative. Now let $(q_k,r_k)$ be quotient and remainder when $x_k$ is divided by $\frac{a_1\cdots a_n}{a_k}$. Then

$$\begin{align*} m &= \sum_{k=1}^nq_k(a_1\cdots a_n)+r_ka_k\\ &= (q_1+\cdots+q_n)\cdot a_1\cdots a_n+\sum_{k=1}^nr_ka_k. \end{align*}$$ Because $r_k\leq\frac{a_1\cdots a_n}{a_k}-1$, we have $q_1+\cdots+q_n>0$ as soon as $m>\sum_{k=1}^na_k\left(\frac{a_1\cdots a_n}{a_k}-1\right)$.

Then $$m=a_1(a_2\cdots a_n(q_1+\cdots+q_n)+r_1)+\sum_{k=2}^nr_ka_k$$ where all coefficients are non-negative.

Note: this technique allows to prove that $$g(a_1,\ldots,a_n)\leq(n-1)a_1\cdots a_n-(a_1+\cdots+a_n).$$ This upperbound is sharp for $n=2$, but weak for $n>2$.