Number Theory Assignment

due Friday, February 4, 2000

1. Find all solutions of the following congruences:

(a) 42x ≡ 0 (mod 72) .

(b) 42x ≡ 5 (mod 72) .

(c) 42x ≡ 18 (mod 72) .

(d) 42^{x} ≡ 36 (mod 72) .

(e) 27^{x} ≡ 9 (mod 72) .

2. Let a, b, and m be integers with m ≥ 2.

(a) Find the general solution of the congruence

ax ≡ 0 (mod m) .

(b) Express the general solution of the congruence

ax ≡ b (mod m)

in terms of a known particular solution u.

3. (a) How many primitive elements are there mod 47?

(b) Find all integers x for which

23^{x} ≡ 3 (mod 47) .

(c) Find the period length of the decimal expansion of the fraction \frac{17}{47}.

4. Consider the primes p in the range 3 ≤ p ≤ 29. Make a table with three columns as follows: (1) the prime p, (2) the smallest positive primitive root c mod p, and (3) the smallest positive integer k for which one has

c^{k} ≡ 2 (mod p) .

5. Find the smallest prime p for which the smallest positive primitive root c is not also primitive mod p^{2}.

Comment. For a given prime p and a given primitive root u mod p there are p congruence classes mod p^{2} that are congruent to u mod p, and, of these, only one is not also primitive mod p^{2}. If one considers the happenstance that c is the one exception among these to be “random”, then the “probability” of this event is \frac{1}{p}. Nevertheless, the answer is greater than 1000. This exercise will require machine computation with arbitrary precision integer arithmetic.

Document network location:

DVI: http://math.albany.edu:8000/math/pers/hammond/course/mat4525s2000/assgt/nt000128.dvi
HTML: http://math.albany.edu:8000/math/pers/hammond/course/mat4525s2000/assgt/nt000128.html