-1
$\begingroup$

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*}$

  • 0
    Thank you for the answer !2012-02-15

2 Answers 2

2

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.

1

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.

  • 0
    In this case, that's still a solution. Thank you !2012-02-14