4
$\begingroup$

I am currently trying to find a primitive element of the multiplicative group of field $GF(p)$. Since the numbers are relatively small, I know the factorization of

$\phi(p)=p-1 = {p_1}^{k_1} {p_2}^{k_2} ... {p_n}^{k_n}$

Wikipedia says that $m\in GF(p)$ is a generator if

$m^{\phi(n)/p_k} \not\equiv 1 \mod p \quad \forall k=1..n$

However, there is no clear explanation why it is the case. Could you please help me to understand this?

  • 0
    You also need to assume (as Wikipedia does) that $m$ is not $0$.2012-05-06

1 Answers 1

2

Can you see that every proper divisor of $\phi(p)$ is a divisor of $\phi(p)/p_k$ for some $k$? So if the order of $m$ isn't $\phi(p)$, then it's a divisor of some $\phi(p)/p_k$?

  • 0
    Continuation. That last bit: if $d$ divides $p-1$ but $d\ne p-1$ then $d=p_1^{r_1}\cdots p_n^{r_n}$ where $r_i\le k_i$ for all $i$ and $r_i\lt k_i$ for at least one $i$; for that $i$, $d$ divides $(p-1)/p_i$.2012-05-06