PROBLEM: Let p be a prime an let k be a positive divisor of p-1. Show that the congruence
x^k≡1 (mod p)
has exactly k solutions (mod p).
Let be a primitive root, and let . Then . (It's easy to see that all of are distinct, so we have solutions.) Moreover if is a solution, we can write for some least nonnegative integer ; and then since we must have and then we have that is one of our solutions above.