NUMBER-THEORY EXERCISES, IX

DAVID PIERCE

Exercise 1. For (ℤ/(17))^{×}:

(a) construct a table of logarithms using 5 as the base;

(b) using this (or some other table, with a different base), solve: (i) x^{15} ≡ 14 (mod 17); (ii) x^{4095} ≡ 14 (mod 17); (iii) x^{4} ≡ 4 (mod 17); (iv) 11x^{4} ≡ 7 (mod 17).

Exercise 2. If n has primitive roots r and s, and gcd(a, n) = 1, prove

log_{s} a ≡ \frac{log_{r} a}{log_{r} s} (mod ϕ(n)).

Exercise 3. In (ℤ/(337))^{×}, for any base, show

log(−a) ≡ log a + 168 (mod 336).

Exercise 4. Solve 4^{x} ≡ 13 (mod 17). Exercise 5. How many primitive roots has 22? Find them. Exercise 6. Find a primitive root of 1250. Exercise 7. Define the function λ by the rules

λ(2^{k}) = \begin{cases}ϕ(2^{k}), & if 0 < k < 3; \\ ϕ(2^{k})/2, & if k ⩾ 3; \end{cases}
λ(2^{k} · p_{1}^{ℓ(1)} ⋯ p_{m}^{ℓ(m)}) = lcm(ϕ(2^{k}), ϕ(p_{1}^{ℓ(1)}), …, ϕ(p_{m}^{ℓ(m)})).

where the p_{i} are distinct odd primes.

(a) Prove that, if gcd(a, n) = 1, then a^{λ(n)} ≡ 1 (mod n).

(b) Using this, show that, if n is not 2 or 4 or an odd prime power or twice an odd prime power, then n has no primitive root.

Exercise 8. Solve the following quadratic congruences.

(a) 8x^{2} + 3x + 12 ≡ 0 (mod 17);

(b) 14x^{2} + x − 7 ≡ 0 (mod 29);

(c) x^{2} − x − 17 ≡ 0 (mod 23);

(d) x^{2} − x + 17 ≡ 0 (mod 23).

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 6, 2007.