MATH 115A Number Theory, HW10 The rst three problems are related to the last few lectures. The last four problems are review problems. 1. R4.6.2(a) and R4.6.2(d) 2. R8.1.4 and R8.1.6 3. I got the following problem and remark from Brian Osserman: Suppose that m = pq, with p, q distinct odd primes. Suppose that for some a with 1 < a < m1, we have am1 1 mod m, but a(m1)/2 1 mod m. Show that (a(m1)/2 1, m) is either p or q. [Remark (not a hint): This exercise is the basic idea behind the fact that if we have both keys d and e of an RSA code, we can factor m.] 4. Solve the polynomial congruence f (x) 0 4 3 mod 162 2 where f (x) = x + 110x + 458x + 135x + 81. 5. Prove that a prime p 3 mod 4 can not be written as the sum of two squares. 6. R7.1.30 7. Suppose a and b are positive integers such that ap | bq , where p > q and (p, q) = 1. Prove a | b. If p and q are not coprime, is it still always true that a | b? 1