NUMBER-THEORY EXERCISES, VIII

DAVID PIERCE

Exercise 1. We have (±3)^{2} ≡ 2 (mod 7). Compute the orders of 2, 3, and −3, modulo 7.

Exercise 2. Suppose ord_{n}(a) = k, and b^{2} ≡ a (mod n).

(a) Show that ord_{n}(b) ∈ {k, 2k}.

(b) Find an example for each possibility of ord_{n}(b).

(c) Find a condition on k such that ord_{n}(b) = 2k.

Exercise 3. This is about 23:

(a) Find a primitive root of least absolute value.

(b) How many primitive roots are there?

(c) Find these primitive roots as powers of the root found in (a).

(d) Find these primitive roots as elements of [−11, 11].

Exercise 4. Assuming ord_{p}(a) = 3, show:

(a) a^{2} + a + 1 ≡ 0 (mod 3);

(b) (a + 1)^{2} ≡ a (mod 3);

(c) ord_{p}(a + 1) = 6.

Exercise 5. Find all elements of [−30, 30] having order 4 modulo 61.

Exercise 6. f(x) ≡ 0 (mod n) may have more than deg(f) solutions: (a) Find four solutions to x^{2} − 1 ≡ 0 (mod 35).

(b) Find conditions on a such that the congruence x^{2} − a^{2} ≡ 0 (mod 35) has four distinct solutions, and find these solutions.

(c) If p and q are odd primes, find conditions on a such that the congruence x^{2} − a^{2} ≡ 0 (mod pq) has four distinct solutions, and find these solutions.

Exercise 7. If ord_{n}(a) = n − 1, then n is prime.

Exercise 8. If a > 1, show n | ϕ(a^{n} − 1).

Exercise 9. If 2 ∤ p and p | n^{2} + 1, show p ≡ 1 (mod 4).

Exercise 10.

(a) Find conditions on p such that, if r is a primitive root of p, then so is −r.

(b) If p does not meet these conditions, then what is ord_{p}(−r)?

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: November 20, 2007.