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.

I have the following task - I have to find all a for which the following system has a solution:

$x \equiv 1\pmod 2$

$x \equiv 2\pmod 3$

$x \equiv a\pmod 5$

I will be very grateful if someone show me the principle behind solving this. By the way, I have some guesses that maybe the LCM is involved.

P.S If I knew the a, how would I solve the system?

Thanks in advance!

share|improve this question
2  
It has a solution for any a. See en.wikipedia.org/wiki/Chinese_remainder_theorem –  Martin Sleziak Apr 13 '11 at 16:37
add comment

2 Answers

up vote 5 down vote accepted

The principle is essentially the Chinese Remainder Theorem. Because the moduli are pairwise coprime, there is a solution for any value of $a$.

But suppose you didn't know the value of $a$. One way to proceed is the following (which is often a faster way of solving such systems rather than the constructive proof of the Chinese Remainder Theorem):

If $x\equiv 1\pmod{2}$, then you must have $x = 1+2r$ for some integer $r$. Plugging that into the second congruence, you have $1+2r\equiv 2\pmod{3}$, or $2r\equiv 1 \pmod{3}$. Multiplying through by $2$ we get $r\equiv 2 \pmod{3}$, so $r$ must be of the $r=2+3s$. Plugging that into $x$, we get that $x$ must be of the form $x = 1+2r = 1+2(2+3s) = 1+4+6s = 5+6s$.

Finally, we plug that into the final congruence. It gives $5+6s\equiv a\pmod{5}$, which is equivalent to $s\equiv a\pmod{5}$. This can always be solved, $s=a+5k$, so the system always has a solution. The solution(s) is $x=5+6s = 5+6(a+5k) = 5+6a + 30k$. that is, $x\equiv 5+6a\pmod{30}$.

share|improve this answer
    
Thanks for the help! –  Petar Minchev Apr 13 '11 at 18:01
add comment

This system of modular equations can be solved by inspection - without rote application of CRT. The first two equations are $\rm\ x \equiv -1\ (mod\ 2,3)\ $ therefore they are equivalent to $\rm\ x\equiv -1\ (mod\ 6)\:.\:$ To solve this and the remaining equation is easy because the moduli $\rm\ m=5\:,\ n=6\ $ are such that one has an obvious inverse modulo the other, viz. $\rm\:6\equiv 1\ (mod\ 5)\:$ hence $\rm\:6^{-1}\equiv 1^{-1}\ \equiv 1\ (mod\ 5)\:.\:$ Therefore, applying EasyCRT below with $\rm\:b = -1\:$ we conclude $$\rm\ x\ \equiv\ b + n\ \bigg[\frac{a-b}{n}\ mod\ m\bigg]\ \equiv\ -1 + 6\ (a+1)\ \equiv\ 5+6a\ \ (mod\ 30)\:.$$

These special cases of CRT, where the RHS is constant, and where one modulus has obvious inverse mod the other, are well worth knowing, since they arise frequently in practice, so they often go a long way towards shortening manual calculations. Below is the EasyCRT that I employ to easily compute the solution when one modulus $\rm\:n\:$ has obvious inverse mod the other $\rm\:m\:.$

THEOREM (EasyCRT) $\rm\ \ $ If $\rm\ m,\:n\:$ are coprime integers then $\rm\ n^{-1}\ $ exists $\rm\ (mod\ m)\ \ $ and

$\rm\displaystyle\quad\quad\quad\quad\quad x\equiv a\ (mod\ m),\ \ x\equiv b\ (mod\ n)\ \ \iff\ \ x\ \equiv\ b + n\ \bigg[\frac{a-b}{n}\ mod\ m\:\bigg]\ \ (mod\ m\:n)$

Proof $\rm\ (\Leftarrow)\ \ \ mod\ n\::\ x\equiv b + n\ (\cdots)\equiv b\:,\ $ and $\rm\ mod\ m\::\ x\equiv b + (a-b)\ n/n \equiv a\:.$

$\rm\ (\Rightarrow)\ \ $ The solution is unique $\rm\ (mod\ m\:n)\ $ since if $\rm\ x',\:x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:m,n\:$ therefore $\rm\ m,\:n\ |\ x'-x\ \Rightarrow\ m\:n\ |\ x'-x\ \ $ since $\rm\ \:m,\:n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = m\:n\:.\quad\quad$ QED

share|improve this answer
add comment

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.