# 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:

1. $d$ is the smallest positive integer of this form
2. 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?

• It seems unlikely to arrive at the greatest common divisor of positive numbers by only additions, without subtractions. I.e. the $x_i$'s should be integers instead of natural numbers in Bezout's identity. Jul 20, 2018 at 20:08
• Yes, you are right, I have modified the original question, it needs to be integers. Jul 20, 2018 at 21:17

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$.
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)?