Answer:
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).
Step-by-step explanation:
