$a_n$ is odd if and only if $n>1$ is a power of a prime $\equiv3\pmod4$. To see this, note that adding the constraints $M=M^T$ and $WMW=M$ for $W=\left(\begin{smallmatrix}&&1\\&1&\\1&&\end{smallmatrix}\right)$ does not change the parity of the number of solutions. With the added constraints you can work out the number exactly (it's always $0$, $2^{\omega(n)}$ or $2^{\omega(n)-1}$), and the only case that gives an odd number is $n=p^k$ with $p\equiv3\pmod4$.

$a_n$ is odd if and only if $n>1$ is a power of a prime $\equiv3\pmod4$. To see this, note that adding the constraints $M=M^T$ and $WMW=M$ for $W=\left(\begin{smallmatrix}&&1\\&1&\\1&&\end{smallmatrix}\right)$ does not change the parity of the number of solutions. With the added constraints you can work out the number exactly (it's always $0$, $2^{\omega(n)}$ or $2^{\omega(n)-1}$), and the only case that gives an odd number is $n=p^k$ with $p\equiv3\pmod4$.

Edit: $a_n-b_n$ is odd iff $n>1$ is of the form $2x^2\pm1$.