Recovering a number from a remainder list

Solution 1:

Hint $ $ It can be done simply without CRT. $\rm\:x\equiv -2\:\ (mod\ \rm3,5)\iff x\equiv -2\equiv 13\pmod{ 15}\:$ Now since $13\equiv 1\pmod 2\:$ we conclude $\rm\:x\equiv 13\:\ (mod\ 2,15)\iff x\equiv 13\pmod{30}\:$

Hence your hunch was correct: it is easy (these are often warm-up exercises to CRT).

Thus this constant case of CRT is solved simply by taking least common multiple of moduli:

$$\rm x\equiv a\ (mod\ m,n)\!\iff\! m,n\:|\:x\!-\!a\!\iff\! lcm(m,n)\:|\:x\!-\!a\!\iff\! x\equiv a\ (mod\: lcm(m,n)) $$

This simple constant-case optimization of CRT arises quite frequently in practice, esp. for small moduli (by the law of small numbers), so it is well worth checking for. For further examples, see here where it simplified a few page calculation to a few lines, and here and here.

Note that I chose to eliminate the largest moduli first, i.e. $\rm\:x\equiv -2\ mod\ 3,5\:$ vs. $\rm\:x\equiv 1\ mod\ 2,3\:$ since that leaves the remaining modulus minimal ($= 2 $ vs. $5$ above), which generally simplifies matters if we need to apply the full CRT algorithm in the final step (luckily we did not above).

Update $ $ Regarding your update: knowing the residues of $\rm\:n\:$ modulo a finite set $\rm\:S\:$ of moduli only determines $\rm\:n\:$ modulo $\rm\:lcm\:S.\:$ However, if $\rm\:S\:$ is infinite (e.g. all primes), then the residues do determine $\rm\:n\:$ uniquely from the residue of any modulus $\rm > n$.

In cases where one is working with bounded size integers such modular representations can prove effective for computational purposes, esp. if the moduli are chosen related to machine word size, so to simplify arithmetic. See any good textbook on computer algebra, which will discuss not only this but many other instances of modular reduction - a ubiquitous technique in algebraic computation.

Solution 2:

This is a classic example of Chinese remainder theorem. To solve it, one typically proceeds as follows. We have $$x = 2k_2 + 1 = 3k_3 + 1 = 5k_5 + 3.$$ Since $\displaystyle x = 2k_2 + 1 = 3k_3 + 1$, we have that $2k_2 = 3k_3$ i.e. $2|k_3$ and $3|k_2$, since $(2,3) = 1$. Hence, $k_3 = 2k_6$ and $k_2 = 2k_6$. Hence, we now get that $$x = 6k_6 + 1 = 5k_5+3.$$ Rearranging, we get that $$6k_6 - 5k_5 = 2.$$ Clearly, $(2,2)$ is a solution to the above. In general, if $ax+by$ has integer solutions and $(x_0,y_0)$ is one such integer solution, then all integer solutions are given by $$(x,y) = \displaystyle \left( x_0 + k \frac{\text{lcm}[\lvert a \rvert,\lvert b \rvert]}{a}, y_0 - k \frac{\text{lcm}[\lvert a \rvert,\lvert b \rvert]}{b} \right)$$ where $k \in \mathbb{Z}$. Hence, all the integer solutions to $6k_6 - 5k_5 = 2$, are given by $$(k_6,k_5) = \left( 2 + 5k, 2 + 6k \right)$$ Hence, $x = 5k_5 + 3 = 30k + 13$ i.e. $$x \equiv 13 \bmod 30.$$