NP-hardness of solving congruence equations in several variables

69 Views Asked by At

You are given the following equation modulo $N$ (where the $\beta_i$'s are given integers modulo $N$, and the $x_i$'s are unknown integers modulo $N$): $$\beta_1x_1 = \beta_2 x_2 = \ldots = \beta_l x_l$$ and you are asked to determine whether there exists $x_1, x_2, \ldots, x_l$ that satisfies the above equation, in such a way that $x_i \in \left[ -\frac{N}{5} , \frac{N}{5} \right]$ (modulo $N$) for all $i$. Note that $l$ is a fixed number. Is this problem NP-hard?

I tried a reduction from 1-in-k SAT, 3SAT, and integer linear programming, but none of my attempts proved successful.