Description

1 Chinese Remainder Theorem Practice
In this question, you will solve for a natural number x such that,
x ≡ 2 (mod 3)
x ≡ 3 (mod 5) (1) x ≡ 4 (mod 7)
(a) Suppose you find 3 natural numbers a,b,c that satisfy the following properties:
a ≡ 2 (mod 3) ; a ≡ 0 (mod 5) ; a ≡ 0 (mod 7), (2) b ≡ 0 (mod 3) ; b ≡ 3 (mod 5) ; b ≡ 0 (mod 7), (3) c ≡ 0 (mod 3) ; c ≡ 0 (mod 5) ; c ≡ 4 (mod 7). (4)
Show how you can use the knowledge of a, b and c to compute an x that satisfies (1).
In the following parts, you will compute natural numbers a,b and c that satisfy the above 3 conditions and use them to find an x that indeed satisfies (1).
(b.i) Find a∗, the multiplicative inverse of 5×7 modulo 3. What do you see when you compute (5×7)×a∗ modulo 3, 5 and 7? What can you then say about (5×7)×(2×a∗)?
(c) Find a natural number b that satisfies (3). In other words: b ≡ 3 (mod 5) and is a multiple of 3 and 7.
(d) Find a natural number c that satisfies (4). That is, c is a multiple of 3 and 5 and ≡ 4 (mod 7). (e) Putting together your answers for Part (a), (b), (c) and (d), report an x that indeed satisfies (1).
2 CRT Decomposition
In this problem we will find 3302 mod 385.
(a) Write 385 as a product of prime numbers in the form 385 = p1 × p2 × p3.
(b) Use Fermat’s Little Theorem to find 3302 mod p1, 3302 mod p2, and 3302 mod p3.
(c) Let x = 3302. Use part (b) to express the problem as a system of congruences (modular equations mod 385). Solve the system using the Chinese Remainder Theorem. What is 3302 mod 385?
3 Baby Fermat
Assume that a does have a multiplicative inverse mod m. Let us prove that its multiplicative inverse can be written as ak (mod m) for some k ≥ 0.
(a) Consider the sequence a,a2,a3,… (mod m). Prove that this sequence has repetitions. (Hint: Consider the Pigeonhole Principle.)
(b) Assuming that ai ≡ aj (mod m), where i > j, what can you say about ai−j (mod m)?
(c) Prove that the multiplicative inverse can be written as ak (mod m). What is k in terms of i and j?