Generalized Bezout's Identity with the constraint coefficient of (+1,-1) I have a following question about the generalized Bezout’s identity in number theory.
If $gcd(a_1, a_2, …, a_n) = d$, then there are integers $x_1, x_2, …, x_n \in \mathbb{Z}$ such that
$d = a_1x_1 + a_2x_2 + … + a_nx_n$      (1)
has the following properties:


*

*$d$ is the smallest positive integer of this form 

*every number of this form is a multiple of $d$


my question is can we modify the generalized Bezout’s identity to come up similar expression but instead of $x_i \in \mathbb{Z}$ to be $x_i \in \{\pm 1\}$ antipodal alphabet? In short is there a polynomial time function $f(a_1, a_2, …, a_n)$ that outputs true or false depending if eq(1) has a solution with $x_1, x_2, …, x_n \in \pm 1$ or not? 
 A: Whether or not such a sequence $(x_i) \in \{\pm 1\}^n$ exists is an NP-complete problem. That it is in NP is clear. To show that it is also NP-hard, we will reduce the subset sum problem to it. 
The subset-sum problem asks, given a sequence $(a_1, \ldots, a_n)$ of natural numbers, and a number $k$, is there a subsequence of the original sequence which adds up to $k$. Rephrasing it in language similar to your problem, it asks if there are $y_i \in \{0, 1\}$ such that
$$
y_1a_1 + \cdots y_na_n = k.
$$
Now clearly this equation is satisfied if and only if the equation
$$
(2y_1 - 1)a_1 + \cdots (2y_n - 1)a_n = 2k - (a_1 + \cdots + a_n)
$$
is satisfied -- but this is an instance of your problem, with $x_i = 2y_i - 1$. 
Hence, no such polynomial-time algorithm exists unless P = NP.
A: One can also say that the complexity of the decision whether eq(1) has a solution or not is the same as solving the eq(1) where the coefficients are $x_i \in \{\pm 1\}$ for $1 \leq i \leq n$. In other words, to find the decision if and only if you solve eq(1)?
