Using the Chinese Remainder Theorem, solve the following simultaneous congruence equations in x. Show all your working. 9x -= 3 mod 15, 5x -= 7 mod 21, 7x -= 4 mod 13.

Question

Using the Chinese Remainder Theorem, solve the following simultaneous congruence equations in x. Show all your working.

9 x \equiv 3 mod 15

,

5 x \equiv 7 mod 21

,

7 x \equiv 4 mod 13

.

Answer 1

Step 1
The given congruence equations are

9 x \equiv 3 mod 15

5 x \equiv 7 mod 21

7 x \equiv 4 mod 13

The first congruence can be converted to

\frac{9 x}{3} \equiv \frac{3}{3} (mod \frac{15}{3})

3 x \equiv 1 mod 5

(By division property

_{(\frac{a}{k} \equiv \frac{b}{k} (mod \frac{n}{gcd (n, k)}))}^{a \equiv b mod n})

Now converting all the congruences from

a x \equiv b mod n

to

x \equiv b mod n

by multiplying b with inverse of a under modulo n.
The obtained congruences are

x \equiv 2 mod 5

x \equiv 7 mod 21

x \equiv 8 mod 13

Where

n_{1} = 5, n_{2} = 21, n_{3} = 13, a_{1} = 2, a_{2} = 7, a_{3} = 8 and gcd (n_{1}, n_{2}, n_{3}) = 1

.
Step 2
Now using Chinese remainder theorem solution is obtained by

x \equiv a_{1} n_{1}^{'} y_{1} + a_{2} n_{2}^{'} y_{2} + a_{3} n_{3}^{'} y_{3} (mod N) \to (\cdot)

Where

N = n_{1} n_{2} n_{3} = 5 \times 21 \times 13 = 1365

and

n_{1}^{'} = \frac{N}{n_{1}} = 273

n_{2}^{'} = \frac{N}{n_{2}} = 65

n_{3}^{'} = \frac{N}{n_{3}} = 105

and

y_{i}

are inverse of

n_{i}^{'}

under modulo

n_{i}

, so calculating

y_{i}

.

y_{1} = 2

y_{2} = 11

y_{3} = 1

Step 3
Now substituting all the values in expression (*) .

x \equiv a_{1} n_{1}^{'} y_{1} + a_{2} n_{2}^{'} y_{2} + a_{3} n_{3}^{'} y_{3} (mod N)

x \equiv 2 \times 273 \times 2 + 7 \times 65 \times 11 + 8 \times 105 \times 1 (mod 1365)

x \equiv 1092 + 5005 + 840 (mod 1365)

Not exactly what you’re looking for? Ask My Question This is helpful 30

Want to know more about Congruence?