Question

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.

Answer 1

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

Explanation: