# Thread: help with short proof

1. ## help with short proof

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

Thanks!

2. Let $\alpha$ be a primitive root, and let $\beta = \alpha^{\frac{p-1}{k}}$. Then $1^k = \beta^k \equiv (\beta^2)^k = \dots = (\beta^{k-1})^k$. (It's easy to see that all of $1, \beta, \beta^2,\dots, \beta^{k-1}$ are distinct, so we have $k$ solutions.) Moreover if $x$ is a solution, we can write $x=\alpha^y$ for some least nonnegative integer $y$; and then since $\alpha^{yk}=1$ we must have $p-1 \mid yk \Rightarrow yk=m(p-1)$ and then we have that $x=\alpha^{\frac{p-1}{k}m}$ is one of our solutions above.