MATH135 Lecture Notes - Lecture 8: Chinese Remainder Theorem, Coprime Integers
14 May 2018
School
Department
Course
Professor
MATH 135 Fall 2015: Extra Practice Set 8
These problems are for extra practice and are not to be handed. Solutions will not be posted but, unlike
assignment problems, they may discussed in depth on Piazza.
•The warm-up exercises are intended to be fairly quick and easy to solve. If you are unsure about any
of them, then you should review your notes and possibly speak to an instructor before beginning the
corresponding assignment.
•The recommended problems supplement the practice gained by doing the corresponding assignment.
Some should be done as the material is learned and the rest can be left for exam preparation.
•A few more challenging extra problems are also included for students wishing to push themselves
even harder. Do not worry if you cannot solve these more difficult problems.
Warm-up Exercises
1. Solve
x≡7 (mod 11)
x≡5 (mod 12)
2. Given the public RSA encryption key (e, n) = (5,35), find the corresponding decryption key (d, n).
3. Express 2−i
3+4iin standard form.
Recommended Problems
1. Solve
3x−2≡7 (mod 11)
5≡4x−1 (mod 9)
2. The Chinese Remainder Theorem deals with the case where the moduli are coprime. We now inves-
tigate what happens if the moduli are not coprime.
(a) Consider the following two systems of linear congruences:
A:n≡2 (mod 12)
n≡10 (mod 18) B:n≡5 (mod 12)
n≡11 (mod 18)
Determine which one has solutions and which one has no solutions. For the one with solutions,
give the complete solutions to the system. For the one with no solutions, explain why no
solutions exist.
(b) Let a1, a2be integers, and let m1, m2be positive integers. Consider the following system of
linear congruences
S:n≡a1(mod m1)
n≡a2(mod m2)
Using your observations in (a), complete the following two statements. The system Shas a
solution if and only if . If n0is a solution to S, then the complete
solution is
n≡.
40
MATH135 Full Course Notes
Verified Note
40 documents
