Find all pairs $(x,y)$ which solve
$$ \left\{ \begin{align} 9x+20y&\equiv0\mod{29}\\ 16x+13y&\equiv0\mod{29} \end{align} \right. $$
So I have written this in the form
$$\begin{pmatrix}9&20\\16&13\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}0\\0\end{pmatrix}\mod{29}$$
But I notice that $\det{A}\equiv0\mod{29}$ so it is not invertible in $\mathbb{F}_{29}$. How do I find a solution to this? I have only been taught to find the inverse of the matrix to find $x$ and $y$.
By Gaussian elimination. Put the system to row-echelon form. Here there are only two rows, so it's easy. Multiply first row by the inverse of $9$ so you get $1$ in the so called pivot location. Now subtract the first row enough many times ($16$ in this case) from the second, so that you get $0$ under the $1$ in the first column.
Now when you have an non-invertible matrix, it happens that you get a zero-row (or you can't choose an invertible pivot variable). Hence you can introduce a free variable for that row, and that stays in the solution (so you have many possible solutions for each value of that free variable).