Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.