Math 312 Worksheet - University Of British Columbia -2016 Page 4
ADVERTISEMENT
1
2
3
4
5
6
7
84
PROBLEM 3 (10 points)
(a) (2pts) State the Chinese Reminder Theorem.
Answer: Let m
, m
, . . . , m
and pairwise coprime. Let
Z
1
2
k
>0
b
, b
, . . . , b
Z. Then the system of congruences
1
2
k
x
b
(mod m
)
1
1
x
b
(mod m
)
2
2
.
.
x
b
(mod m
)
k
k
has a unique solution modulo m
m
. . . m
.
1
2
k
1
(b) (8pts) Compute 13
(mod 55) using the Chinese reminder
theorem.
Answer: We want to find an integer x satisfying the congruence
13x
1 (mod 55). Since 55 = 5 11 such integer x will also satisfy the
congruences
3x
1 (mod 5)
and
2x
1 (mod 11).
Note that 2 is the inverse of 3 mod 5 and 6 is the inverse of 2 mod 11.
Then, the previous congruences are equivalent to
x
2 (mod 5)
and
x
6 (mod 11).
We now compute the solution. Let M = 5 11 = 55, M
= 11 and
1
M
= 5. The congruences
2
11x
1 (mod 5)
and
5x
1 (mod 11)
have solutions y
= 1 and y
= 9, respectively. We conclude that the
1
2
unique solution modulo M is
x
2 11 1 + 6 5 9
22 + 270
22 + 50
77
17 (mod 55)
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education