Number Theory Assignment

due Friday, February 4, 2000

  1. Find all solutions of the following congruences:

    1. 42 x = 0 (mod 72) .

    2. 42 x = 5 (mod 72) .

    3. 42 x = 18 (mod 72) .

    4. 42^{x} = 36 (mod 72) .

    5. 27^{x} = 9 (mod 72) .

  2. Let a, b, and m be integers with m >= 2.

    1. Find the general solution of the congruence

      a x = 0 (mod m) .

    2. Express the general solution of the congruence

      a x = b (mod m)

      in terms of a known particular solution u.

    1. How many primitive elements are there mod 47 ?

    2. Find all integers x for which

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

    3. Find the period length of the decimal expansion of the fraction {17}/{47}.

  3. 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) .

  4. 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 {1}/{p}. Nevertheless, the answer is greater than 1000. This exercise will require machine computation with arbitrary precision integer arithmetic.


AUTHOR  |  COMMENT