NUMBER-THEORY EXERCISES, XI

DAVID PIERCE

Exercise 1. Compute the Legendre symbols (91/167) and (111/941).

Exercise 2. Find (5/p) in terms of the class of p modulo 5.

Exercise 3. Find (7/p) in terms of the class of p modulo 28.

Exercise 4. The nth Fermat number, or F_{n}, is 2^{2^{n}} + 1. A Fermat prime is a Fermat number that is prime.

(a) Show that every prime number of the form 2^{m} + 1 is a Fermat prime.

(b) Show 4^{k} ≡ 4 (mod 12) for all positive k.

(c) If p is a Fermat prime, show (3/p) = −1.

(d) Show that 3 is a primitive root of every Fermat prime.

(e) Find a prime p less than 100 such that (3/p) = −1, but 3 is not a primitive root of p.

Exercise 5. Solve the congruence x^{2} ≡ 11 (mod 35).

Exercise 6. We have so far defined the Legendre symbol (a/p) only when p ∤ a; but if p | a, then we can define (a/p) = 0. We can now define (a/n) for arbitrary a and n: the result is the Jacobi symbol, and the definition is

(\frac{a}{n}) = ∏_{p}(\frac{a}{p})^{k(p)}, where n = ∏_{p} p^{k(p)}.

(a) Prove that the function x ↦ (x/n) on ℤ is completely multiplicative in the sense that (ab/n) = (a/n) · (b/n) for all a and b (not necessarily co-prime).

(b) If gcd(a, n) = 1, and the congruence x^{2} ≡ a (mod n) is soluble, show (a/n) = 1.

(c) Find an example where (a/n) = 1, and gcd(a, n) = 1, but x^{2} ≡ a (mod n) is insoluble.

(d) If m and n are co-prime, show

(\frac{m}{n}) · (\frac{n}{m}) = (−1)^{k}, where k = \frac{m − 1}{2} · \frac{n − 1}{2}.

Mathematics Dept, Middle East Tech. Univ., Ankara 06531, Turkey E-mail address: dpierce@metu.edu.tr URL: http://www.math.metu.edu.tr/~dpierce/

Date: December 18, 2007.