Number Theory : Solve the system of congruence $28x+17y\equiv 18 \pmod{41}$ and $31x+11y\equiv 35\pmod{41}$

Starting from your result of

$$219y \equiv -422 \pmod{41} \tag{1}\label{eq1A}$$

the first thing I recommend doing is reducing the coefficients to smaller values since these are generally easier to deal with, plus sometimes you may be able to find simplifications you can use, such as common factors relatively prime to $41$ so they can be "removed" using their multiplicative inverses. Doing this, and using that $\gcd(2, 41) = \gcd(7, 41) = 1$, gives

$$\begin{equation}\begin{aligned} 14y & \equiv -12 \pmod{41} \\ 7y & \equiv -6 \pmod{41} \\ 7y & \equiv 35 \pmod{41} \\ y & \equiv 5 \pmod{41} \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

Using this result in your first congruence equation, along with $\gcd(28, 41) = 1$, gives

$$\begin{equation}\begin{aligned} 28x + 85 & \equiv 18 \pmod{41} \\ 28x + 3 & \equiv 18 \pmod{41} \\ 28x & \equiv 15 \pmod{41} \\ 28x & \equiv 56 \pmod{41} \\ x & \equiv 2 \pmod{41} \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

In general, though, if you can't fairly easily simplify the results as I did above, you can instead use something like either the constructive proof or direct proof methods described in Wikipedia's "Chinese remainder theorem" article.


Alternatively, use linear algebra. The system is $$ \begin{pmatrix} 28 & 17 \\ 31 & 11 \end{pmatrix} \begin{pmatrix} x \\ y\end{pmatrix} = \begin{pmatrix} 18 \\ 35 \end{pmatrix} $$ The inverse of the matrix is $$ -\frac{1}{219}\begin{pmatrix} \hphantom-11 & -17 \\ -31 & \hphantom-28 \end{pmatrix} $$ It remains to find the inverse of $219$ mod $41$, which is $3$ by the extended Euclidean algorithm.


$$-13x+17y\equiv 18 \pmod{41}\tag1$$ $$-10x+11y\equiv -6 \pmod{41}\tag2$$

$(1)\times 10-(2)\times 13$ $$ 27y\equiv 12 \pmod{41} \implies y \equiv \frac{12}{27} \equiv \frac{4}{9} \equiv \frac{20}{45} \equiv \frac{20}{4} \equiv 5 \pmod{41} $$

$$ x \equiv \frac{11y+6}{10}\equiv \frac{61}{10} \equiv \frac{20}{10} \equiv 2 \pmod{41}.\blacksquare $$