# Modular equations system

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?

-
It has a solution for any a. See en.wikipedia.org/wiki/Chinese_remainder_theorem – Martin Sleziak Apr 13 '11 at 16:37

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

-
Thanks for the help! – Petar Minchev Apr 13 '11 at 18:01

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

-