help with short proof

**matzerath** · March 16th 2010, 12:31 PM

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!

**Bruno J.** · March 16th 2010, 12:56 PM

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.

Thread: help with short proof

LinkBack

Thread Tools

Display

help with short proof

Similar Math Help Forum Discussions

Short proof ?

Two short Questions

Short Inductive Proof

Short proof that rows-rank=column-rank?

short proof

Search Tags