Find solutions of $a + b + c$ even, $3a + 2b - 3c$ odd, $a - 7b + 8c$ odd, in polynomial time

Question

Suppose I have a linear equation in $3$ variables $a$, $b$ and $c$.

\begin{align} \begin{cases} a + b + c &= 40 \\ 3a + 2b - 3c &= 49 \\ a - 7b + 8c &= 77 \end{cases} \end{align}

The solution to the above system can be found using the usual means and is $a=24, b=5, c=11$.

However, if I rewrite the same system in the below form

\begin{align} \begin{cases} a + b + c &= \textrm{even number} \\ 3a + 2b - 3c &= \textrm{odd number} \\ a - 7b + 8c &= \textrm{odd number} \end{cases} \end{align}

Can a solution be found in polynomial time without using brute force techniques ? If yes, can the equation be extended to higher order and still solutions be found in polynomial time ?

Multiple solutions may exist but I want to know the process.

Answer 1

Solve the system in $\mathbf Z/2\mathbf Z$. Run the full row reduction algorithm on its augmented matrix:

$$ \left[\begin{array}{ccc|c} 1&1&1&0\\ 1&0&1&1\\1&1&0&1 \end{array}\right]\rightsquigarrow\left[\begin{array}{ccc|c} 1&1&1&0\\ 0&1&0&1\\0&0&1&1 \end{array}\right]\rightsquigarrow\left[\begin{array}{ccc|c} 1&1&0&1\\ 0&1&0&1\\0&0&1&1 \end{array}\right]\rightsquigarrow\left[\begin{array}{ccc|c} 1&0&0&0\\ 0&1&0&1\\0&0&1&1 \end{array}\right]$$

The solution is the last column. It means: $$a~\text{even}, \quad b~\text{and}~c~\text{odd}.$$