Solving a system of equations with boolean variables in $\mathbb{Z}_3$ I have a problem that reduces to a system of $2n+1$ equalities on $4n$ variables all in $\mathbb{Z}_3$, where the variables are constrained to be in $\{0,1\}$, i.e.,
$$x_1 + x_2 + ... + x_k \equiv a\ (\mathrm{mod}\ 3)$$
$$x_2 + x_3 + ... + x_l \equiv b\ (\mathrm{mod}\ 3)$$
$$\cdots$$
$$x_m + ... + x_{4n} \equiv c\ (\mathrm{mod}\ 3)$$
The right hand side ($a$, $b$, $c$, $\ldots$) is known, but not necessarily in $\{0,1\}$ but in $\{0,1,2\}$.
I have found no better way of solving this
but a brute-force approach on the free variables, because doing Gaussian elimination, I can get a an upper triangular system, but that would only give me a solution if my variables were in $\{0,1,2\}$.
So my question is whether there is a more efficient, polynomial-time, way to solve this system that I may have missed? If not is there a complexity result that shows this problem to be hard in the general case ?
 A: If I understand correctly, you want to find a solution to the system :
$$Ax = b$$
Where $A$ is a binary matrix, $x = (x_1, x_2, ... , x_n)^T$ a vector of variables, and $b = (b_1, b_2, ..., b_m)$ a vector of right-hand side, with $b_i \in \{0, 1, 2\} \; \forall i \in \{1, ..., m\}$.
If so, you want to solve an Integer Program.
Unfortunately integer programs are NP-Complete in general, and your special case includes the set-partitioning problem, which is also NP-complete.
How to solve it
Because integer programs have a lot of real-life applications, specialized algorithms and software have been devised to solve them. In my experience, solving a problem with fewer than 1000 variables should take less than a second, but it really depends on the problem... The solvers offering the highest performances are probably cplex or gurobi (they are not free, but I think they offer a free student version). There are also open source solvers such as GLPK and lp_solve. If you have a relatively small problem (maybe less than 100 variables), you can even use the Excel solver, although it really not the best!
In any case, you do not want to code it yourself. Those software have decades of improvments into them and that is why they work well.
How the algorithm works 
Every commercial solver solves the problem by branch-and-bound.

A branch-and-bound algorithm consists of a systematic enumeration of
candidate solutions by means of state space search: the set of
candidate solutions is thought of as forming a rooted tree with the
full set at the root. The algorithm explores branches of this tree,
which represent subsets of the solution set. Before enumerating the
candidate solutions of a branch, the branch is checked against upper
and lower estimated bounds on the optimal solution, and is discarded
if it cannot produce a better solution than the best one found so far
by the algorithm.

Your problem is a feasibility problem and not an optimization problem, so there is no need to compute bounds. However, the algorithm has to check wheather the current branch is infeasible. This is usually done by solving a linear relaxation of the problem (accepting solutions with fractional variables).
Commercial solvers also use many tricks to reduce to speed up the algorithm. Unfortunately, many of those tricks are secrets!
