Question

Problem 1 Use the Chinese remainder theorem, find all integers x such that: (20 pts) x = 1 (mod 5) r = 2 (mod 7) x = 3 (mod 9) I= 4 mod 11) Answer,

Answer 1

All the congruences are of the form

a (mod d)

We see that in all the congruences the moduli are relatively prime because because 5, 7,9,11 have no common factor other than 1.

Let M5 x 7 x 9 x 11 3465

Let m17 x 9 x 11 693

Let m2 5 x 9 x 11 495

Let m3 =5 x 7 x 11 385

Let m4=5 x 7x 9 =315

Let y be the inverse of ml modulo 5

m1 X y 1mod 5 693 x y1 1mod 5 12

The above expression simply means that what should be the value for y₁ such that when multiplied with m₁ and then divided by 5, the remainder should be 1.

Similarly

m2 X y2 1mod 7 495 x y2 1mod 7 y2- 3

$m_{3}\times y_{3}\equiv 1\,mod\,\,9\Rightarrow 385\times y_{3}\equiv 1\,mod\,\,9\Rightarrow y_{3}=4$

$m_{4}\times y_{4}\equiv 1\,mod\,\,11\Rightarrow 315\times y_{4}\equiv 1\,mod\,\,11\Rightarrow y_{4}=8$

a1 X m1 X y1 a2 X m2 X y2 a3 X m3 X y3 + a4 X m4 X y4

Substituting the values , we get

$x=1\times 693\times 2\,+\,2\times 495\times 3\,+\,3\times 385\times 4\,+\,4\times 315\times 8$

$x=19056$

So the solution is

19056 (mod M