## Description

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