Math 422: Introduction to Number Theory
Homework on 20
A. Silverman 20.3.
B. Suppose that p is a prime with p ≡ 1 (mod 3). Let a ∈ Z with p - a.
(a) Show that if a is a cubic residue, then a
(p−1)/3 ≡ 1 (mod p).
(b) Show the converse.
C. Write a program that implements the CRT for an arbitrary list of moduli.
The input should be a list of ordered pairs [(a1, m1),(a2, m2), . . . ,(an, mn)]
where the mi are pairwise relatively prime, and the output should be a
such that a ≡ ai (mod mi) for all i. Remember to prove your algorithm
works!
D. Let f(x) be a polynomial, and suppose m, n ∈ N with gcd(m, n) = 1. Show
that f(x) ≡ 0 (mod mn) has a solution if and only if f(x) ≡ 0 (mod m)
and f(x) ≡ 0 (mod n) both have solutions.
E. (a) Find all solutions to x
2 ≡ 1 (mod 143) using the Chinese Remainder
Theorem.
(b) Let p, q be distinct primes. How may solutions does x
2 ≡ 1 (mod pq)
have?
(c) Let p1, p2, . . . , pr be distinct primes. How many solutions does x
2 ≡ 1
(mod p1p2 · · · pr) have?
1 of 1
