Satisfiability of at least k linear equations over Z2 is NP-hard Given a system of $m$ equations in $n$ boolean variables:

$$\begin{align}
a_{11}x_1 + a_{12}x_2 + \dots +a_{1n}x_n &amp;= b_1\pmod2\\
a_{21}x_1 + a_{22}x_2 + \dots +a_{2n}x_n &amp;= b_2\pmod2\\
&amp;\;\vdots\\
a_{m1}{x_1} + a_{m2}x_2 + \dots +a_{mn}x_n &amp;= b_m\pmod2
\end{align}$$

Where all $a_{ij}, x_i$ and $b_i$ are $0$ or $1$, I want to prove that the decision problem of finding if there is a vector $x$ that satisfies at least $k$ equation, is NP hard.

I was given a hint to reduce from 3-SAT, so I am trying to build from each clause in the 3-SAT formula several equations, such that a constant number of them is satisfied iff the clause is satisfied. But I am not sure how to impose this restriction of a constant number of equations satisfied (for all different truth assignments that satisfy the given clause).
Consider any clause $x \lor y \lor z$, and the following table:
$$
\begin{array}{c|c|c|c}
\text{satisfied literals} &amp; [x]+[y]+[z] &amp; [x\oplus y] + [x\oplus z] + [y\oplus z] &amp; [x\oplus y\oplus z] \\\hline
0 &amp; 0 &amp; 0 &amp; 0 \\\hline
1 &amp; 1 &amp; 2 &amp; 1 \\\hline
2 &amp; 2 &amp; 2 &amp; 0 \\\hline
3 &amp; 3 &amp; 0 &amp; 1
\end{array}
$$
Here $[x]$ is 1 if $x$ is satisfied and 0 otherwise.

The first row sums to 0, and the rest sum to 4 (ignoring the column labeled "satisfied literals"). Can you use this to your advantage?