# Linear congruences system

How do I solve a four-equation linear congruence system like the one below ? \begin{align*} a-2d &\equiv 5 \pmod{10}\\ -3a+3d &\equiv 8 \pmod{10}\\ 4a-4d &\equiv 6 \pmod{10}\\ -5a+d &\equiv 4 \pmod{10} \end{align*}

-
Same way you solve a regular system of linear equations, only doing operations modulo $10$; just remember that you are not allowed to multiply/divide, except by numbers that are invertible modulo $10$ (that is, odd numbers that are not multiples of $5$). – Arturo Magidin Feb 14 '12 at 22:05
What does invertible modulo n exactly mean ? – Skydreamer Feb 14 '12 at 22:49
$r$ is invertible modulo $n$ means there exists $s$ such that $rs\equiv1\pmod n$. E.g., $3$ is invertible modulo $10$, but $4$ isn't. – Gerry Myerson Feb 15 '12 at 0:09
Thank you for the answer ! – Skydreamer Feb 15 '12 at 9:56

For variety, here is another method: solve the system modulo $2$ and modulo $5$ then use CRT (Chinese Remainder) to deduce the solution mod $10$.

Mod $2\:$ it's $\:a\equiv 1,\ a+d\equiv 0,\ 0\equiv 0,\ a+d\equiv 0\$ with solution $a\equiv 1\equiv d.\:$

Mod $5\:$ it's $\: a\equiv 2d,\ 2a-2d\equiv -2,\: -a+d\equiv 1,\ d\equiv -1\:$ with solution $\:a\equiv 3,\: d\equiv -1$.

Thus $\:d\equiv -1\pmod{5},\ d\equiv -1\pmod 2\ \Rightarrow\ d\equiv -1 \pmod{ 10}$

and $\:\ \ a\:\equiv\: 3\ \pmod{5},\:\ a\:\equiv\: 3\:\pmod 2\ \Rightarrow\ a\:\equiv\: 3\: \pmod {10}$.

Note that, due to the law of small numbers, the systems mod $2$ and $5$ are so simple that they can be solved mentally - a great advantage of applying such "divide and conquer" methods like CRT. Above I exploited the freedom of choice of congruence class representives to choose $\:-1\:$ vs. $\:4\pmod 5,$ in order to enable a constant-case optimization of CRT. See here for more on this, including an example which simplifies a three-page CRT calculation to a trivial three-line calculation.

-

Arturo's answer in the comments is fine. There is a method available for congruences that is not available with equations, namely, trying all the possible answers. Look at your 1st congruence. For each of the 10 possible values of $d$, you get a unique value of $a$, so there are only 10 $(a,d)$ pairs that could possibly work. You can try each of those pairs in the other equations to see which, if any, survive.

I don't recommend this method when the modulus and/or number of unknowns is too large for the computing resources available, but for a problem this small it is one reasonable way to go.

-
In this case, that's still a solution. Thank you ! – Skydreamer Feb 14 '12 at 22:42