2.3. Let g be a primitive root for Fp. (a) Suppose that x = a and x = b are both integer solutions to the congruence gx ≡ h (mod p). Prove that a ≡ b (mod p - 1). Explain why this implies thatHoffstein, Jeffrey.

Let p be a prime number. Suppose that a and n are positive numbers such that gcd (a, p) = 1 and gcd (n, p - 1) = 1.

Determine the number of solutions of the congruence x n ≡ a (mod p). Solution.

Let g be a primitive root modulo p. Since gcd (a, p) = 1, we can find an integer l such that a ≡ g l (mod p). In addition, since x ≡ 0 (mod p) is not a solution, we can write x ≡ g k (mod p) for some integer k.

Now the congruence can be written as g kn ≡ g l (mod p), which is equivalent to kn ≡ l (mod p - 1). This congruence can be solved in k by k ≡ ln-1 (mod p - 1) as gcd (n, p - 1) = 1, yielding a unique solution x ≡ g k (mod p) of the congruence x n ≡ a (mod p).