Reducing $Ax = u \vee Ax = v$ to $By = w$ Let $\mathbb{Z}_2 = \{0,1\}$ be the integers mod $2$. Let $A \in \mathbb{Z}_2^{m \times n}$ and $u,v \in \mathbb{Z}_2^m$. Consider the problem of determining whether there is a vector $x \in \mathbb{Z}_2^n$ such that $$Ax = u \vee Ax = v.$$
One can reduce this problem to the problem of determining whether there is a solution to this system:
$$
\begin{pmatrix}
0 & \ldots & 0 & 1 & 1 \\
A_{1,1} & \ldots & A_{1,n} & u_1 & v_1 \\
\vdots  & \ddots & \vdots  & \vdots & \vdots \\
A_{m,1} & \ldots & A_{m,n} & u_m & v_m \\
­\end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\ x_n \\ y_1 \\ y_2\end{pmatrix} = \begin{pmatrix}1 \\ 0 \\ \vdots \\ 0\end{pmatrix}
$$
since each line gives $A_i \cdot x = y_1 u_i + y_2 v_i$ and $(y_1, y_2) \in \{(0,1), (1,0)\}$.
I wonder if there is such a strategy to reduce $Ax = u \vee Ax = v$ to $By = w$ over $\mathbb{Z}_3$.
 A: There is not. The solutions to a system of linear equations form an affine subspace, whose intersection with another affine subspace is again an affine subspace, and over a finite field $\mathbb F$ the cardinality of an affine subspace is a power of $|\mathbb F|$. If $Ax=u$ and $Ax=v$ both have solutions, they both have the same number of solutions, and if $u\neq v$, the solutions are all distinct, so the total number of solutions for the disjunction is twice the number for the individual equations. In the case of $\mathbb Z_2$, that's OK, since you can write a system with twice as many solutions. You can't do this in the case of $\mathbb Z_3$, at least not with a vector consisting of the $x_i$ and some auxiliary variables, since the resulting set of solutions for the $x_i$ is the intersection of an affine subspace with the affine subspace of solutions for the entire vector, whose cardinality is a power of $3$, whereas the cardinality of the desired solution set is twice a power of $3$.
