Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Math 3527 Number Theory 1

Spring 2024

Homework 11

due Fri Apr 19th.

Psrt I: No justi cations are required for these problems. Answers will be graded on correctness.

1. Calculate the following Jacobi symbols (i) using the de nition in terms of Legendre symbols, and (ii) using quadratic reciprocity for Jacobi symbols:

(a) (51/5).

(b) (51/3).

(c) (777/433).

(d) Which method is easier to implement by hand?

2. Calculate the following Legendre symbols (i) using quadratic reciprocity for Legendre symbols by factoring the top number at each stage, and (ii) using quadratic reciprocity for Jacobi symbols:

(a) (47/15).

(b) (1423/231).

(c) (6733/1633).

(d) Which method is easier to implement by hand?

3. Do the following (make sure to give enough details to show that you actually used the requested algorithm):

(a) Use Berlekamp's root- nding algorithm to  nd the roots of the polynomial x2  = 38 (mod 109). (b) Use the Solovay-Strassen test with a = 3 to test whether m = 2773 is composite.

(c) Use the Solovay-Strassen test with a = 1149 to test whether m = 6601 is composite.  (d) Use the Solovay-Strassen test with a = 2, 3, 5 to test whether m = 1729 is composite.

Psrt II: Solve the following problems. Justify all answers with rigorous, clear explanations.

4. The goal of this problem is to classify the prime divisors of integers of the form n2 + n - 3.

(a) Let p be a prime. Prove that 13 is a square modulo p if and only if p = 2, p = 13, or p is congruent to 1, 3, 4, 9, 10, or 12 modulo 13.

(b) Prove that a prime p divides an integer of the form q(n) = n2  + n - 3 if and only if p =  13 or p is congruent to 1, 3, 4, 9, 10, or 12 modulo 13. [Hint: What do you have to take the square root of?]

5.  The goal of this problem is to prove that there are in  nitely many primes congruent to 4 modulo 5.

(a)  Let n be a positive integer and let pbe a prime dividing 5(n!)2 — 1. Show that p > nand that (p/5)  = +1. (b)  Show that 5(n!)2  — 1 has at least one prime divisor not congruent to 1 modulo 5, and deduce that it has a prime divisor greater than n that is congruent to 4 modulo 5.

(c)  Deduce that there are in  nitely many primes congruent to 4 modulo 5.  [Hint:  If P were the largest, apply (b) to n = P.]

6.  As shown on problem 6 of homework 2, the only primes of the form ak — 1 are those numbers 2p — 1 where p is prime, but as seen in problem 4 of homework 7, not all of these numbers actually are prime. The goal of this problem is to show the non-primality of some of these values 2p — 1.

(a)  Suppose that q 三 7 (mod 8) is prime.  Show that q divides 2(q- 1)/2 — 1. [Hint: Euler's criterion.]

(b)  Suppose that p 三 3 (mod 4) is a prime such that 2p + 1 is also prime, and p > 3.  Show that 2p  — 1 is composite.

(c)  Deduce that 2p  — 1 is composite for the primes p = 11, 23, 83, 131, 179.

7.  The goal of this problem is to give several di  erent proofs of the fact that if p 三 1  (mod 4) is a prime, then the congruence x2  三 — 1 (mod p) has a solution.  In class, this was proven using primitive roots.

(a)  Show that if x = [2/p-1! then x2 三 — 1  (mod p).  [Hint:  Note that  (p — 1)! =  [1 · 2 · · · · · 2/p-1] · [(p — 2/p-) · · · (p-2)(p-1)]

(b)  Show that if p 三 1 (mod 4), then — 1 is a quadratic residue modulo p.  [Hint:  Euler's criterion.]

(c)  Suppose that a is any quadratic non-residue modulo p.  Show that x = a(p- 1)/4  has x2  三 — 1  (mod p). [Hint: Euler again.]