Use the construction in the proof of the Chinese remainder theorem

Question

20. Use the construction in the proof of the Chinese remainder theorem to find all solutions to the system of congruences x ≡ 2 (mod 3), x ≡ 1 (mod 4), and x ≡ 3 (mod 5).

I am not sure what is the process of answering this question!?

Answer 1

There are multiple proofs of the Chinese Remainder Theorem; some of them demonstrate how to construct a particular solution $x^*$ of any system of congruences. This can then be used to describe all integer solutions to the system of congruences in question.

You will have to refer to your text's proof to perform the construction, but to give an example, here is one such construction (reference: Andrew Adler, The Theory of Numbers):

Take the congruences $x \equiv a_i \pmod{m_i}$ for $1 \leq i \leq r$ where the $m_i$ are pairwise relatively prime ($\gcd(m_i,m_j) = 1$ for $i \neq j$). Let $m = m_1\dots m_r$. Then, find all $b_i$ where:

$$(m/m_i)b_i \equiv 1 \pmod{m_i}$$

which is solvable since $\gcd(m/m_i, m_i) = 1$. Then, a particular solution is:

$$x^* = \sum_{i = 1}^r (m/m_i)a_ib_i$$

which satisfies $x^* \equiv a_i \pmod{m_i}$ for all $1 \leq i \leq r$. Then, by the Chinese Remainder Theorem, you know that the set of all solutions is $x^* + mt$ for all $t \in \mathbb{Z}$.

Answer 2

Remainders :

r1 = 2

r2 = 1

r3 = 3

Multiply all the divisors as M:

M = 3*4*5 = 60

a1 = 60/3 = 20

a2 = 60/4 = 15

a3 = 60/5 = 12

NOW Inverse:

i1 = 20 mod 3 (inverse) = 2

i2 = 15 mod 4 (inverse) = 3

i3 = 12 mod 5 (inverse) = 3

Z = (i1.r1.a1)+(i2.r2.a2)+(i3.r3.a3)

Z = (2*2*20) + (3*1*15) + (3*3*12)

Z = 233

233 = x mod M

233 = x mod 60

Simply divide 233 by 60 and then the answer is the remainder:

x = 53. Answer