Given $x_1, \ldots , x_n \in \mathbb{Z}$ with $\gcd (x_1, \ldots, x_n) = d$, I'll call any sum of the form $$ \sum_{i = 1}^n x_i y_i = d $$ with $y_1, \ldots, y_n \in \mathbb{Z}$ a Bezout sum.
For all $n$, does there exist a set of $n$ integers $x_1, \ldots, x_n$ such that for every possible Bezout sum $\sum_i x_i y_i = d$ all of the $y_i$ are nonzero?
Clearly this holds for $n = 2$. Just take $x_1 = 2$ and $x_2 = 3$.
For $n = 3$, I stumbled on the example $42, 72, 600$. The reason this works is that the $\gcd$ of any $2$ numbers is strictly greater than the $\gcd$ of all $3$.
I think I've been able to show that a sufficient condition for $x_1, \ldots, x_n$ to work is that $ \gcd (a_1, \ldots, a_{n -1})$ is strictly greater than $\gcd(x_1, \ldots, x_n)$ for all $\{a_1, \ldots, a_{n - 1}\} \subset \{x_1, \ldots, x_n\}$. Is this condition necessary? Can we always find a set of $n$ numbers that satisfies the proposed sufficient condition?
Any insight would be greatly appreciated.
The condition is both necessary and sufficient.
As you note, if there is a proper subset $x_{i_1},\ldots,x_{i_k}$ such that $\gcd(x_{i_1},\ldots,x_{i_k}) = \gcd(x_1,\ldots,x_n)$, then express the greatest common divisor as a linear combination of $x_{i_1},\ldots,x_{i_k}$, and then extend it to a linear combination of $x_1,\ldots,x_n$ by adding zeros to the remaining $x_j$. This shows necessity.
For sufficiency, suppose $x_1,\ldots,x_n$ are given, and that $d=\gcd(x_1,\ldots,x_n)$ is expressed as a sum, $$d = \sum_{i=1}^n x_iy_i.$$ If any coefficient is zero, say $y_1=0$, then $d = \sum_{i=2}^n x_iy_i$, and hence $\gcd(x_2,\ldots,x_n)|d = \gcd(x_1,\ldots,x_n)$. But since $\gcd(x_1,\ldots,x_n)|\gcd(x_2,\ldots,x_n)$ also holds, it follows that $\gcd(x_2,\ldots,x_n) = d = \gcd(x_1,\ldots,x_n)$, giving the contrapositive of your condition.
For an example with this property for any $n$, let $p_1\lt\cdots\lt p_n$ be $n$ distinct primes, and for each $i$, let $x_i = \frac{1}{p_i}(p_1\cdots p_n)$. Note that $p_i$ divides $x_j$ for all $j\neq i$, but no $p_k$ divides all $x_i$. Thus, $\gcd(x_1,\ldots,x_n) = 1$, but $\gcd(x_1,\ldots,\hat{x_k},\ldots,x_n) = p_k$, where $\hat{x_k}$ denotes that we are omitting $x_k$ in the list.
So an easier example for $n=3$ would be $x_1=15$, $x_2=10$, $x_3=6$, which has the same pattern as your example for $n=2$.
In fact, that example is "minimal" in the sense mentioned in the comments. Without loss of generality, assume all $x_i$ are positive.
First, if $\gcd(x_1,\ldots,x_n)=d\gt 1$, then we can replace each $x_i$ by $\frac{x_i}{d}$ to get an example with smaller $x_i$. Thus, we may take $\gcd(x_1,\ldots,x_n)=1$.
Now, let $d_i = \gcd(x_1,\ldots,\hat{x_i},\ldots,x_n)$. Each of these must be greater than $1$. Note that if $i\neq j$, then $\gcd(d_i,d_j) = 1$, since $d_i$ divides all $x_k$ except for $x_i$, and similarly with $d_j$. Thus, $\gcd(d_i,d_j)$ divides all $x_i$, and hence must be $1$.
Now assume that $p$ is a prime factor of $d_i$, but $d_i\neq p$. Then we can replace each $x_j$, $j\neq i$, with $\frac{x_i}{d_i}$. That will maintain $\gcd(\frac{x_1}{p},\ldots,\hat{\frac{x_i}{p}},\ldots,\frac{x_n}{p})=\frac{d_i}{p}\gt 1$, but since $p$ does not divide $d_j$ for $j\neq i$, it does not affect the value of any other $d_j$. We would still have $\gcd(x_1,\ldots,x_n)=1$ since we have only reduced the prime divisors of some of the $x_i$. This would in turn give again a smaller example.
Thus, we may also assume that $d_i=p_i$ is prime for each $i$, with $p_i\neq p_j$ if $i\neq j$. Thus, $x_j$ is divisible by $$ \prod_{\stackrel{i=1}{i\neq j}}^n p_i.$$ Setting $x_j$ equal to that product yields an example, and by the above we can't have an example with fewer prime factors involved. Thus, the minimal example is obtained with the formula above, and setting $p_k$ to be the $k$th prime.