# Use the construction in the proof of the Chinese remainder theorem

1. 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!?

• To built the solution $x$ you have to remark that for three integers $a,b,c$ that $\gcd(bc,ac,ab)=1$ and use Bachet-Bézout relations ! Sep 28 '16 at 17:00
• Add that $a,b,c$ must be pairwise coprime ! Sep 28 '16 at 17:57

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:

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

• To build the solution you can also use the lemma in my comment ! Sep 28 '16 at 19:38