Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Where does Wikipedia say this? –  Chris Eagle May 6 '12 at 10:15
    
Fixed the question, thanks for the comment! –  wh1t3cat1k May 6 '12 at 10:19
    
You also need to assume (as Wikipedia does) that $m$ is not $0$. –  Chris Eagle May 6 '12 at 11:43
add comment

1 Answer

up vote 2 down vote accepted

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$?

share|improve this answer
    
Could you please get into a bit more detail in here? I can't figure out what these divisors are about. Maybe I lack something fundamental here –  wh1t3cat1k May 6 '12 at 12:30
    
Well, that's the question: what do you know, and what don't you know, about raising numbers to powers modulo a prime? It's hard to give an answer that will help you when you volunteer no information. Anyway, here are a few facts you'll find proved in any intro number theory text: $m$ in $F_p$, $m\ne0$ implies $m^{p-1}=1$; smallest positive $d$ such that $m^d=1$ is a divisor of $p-1$; $m$ is a primitive element (i.e., generator) is the same as $d=p-1$; if $d=p-1$ then $d$ doesn't divide $(p-1)/p_k$; if $d$ divides $p-1$ but $d\ne p-1$ then $d$ divides some $(p-1)/p_k$. Continued.... –  Gerry Myerson May 6 '12 at 13:03
    
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$. –  Gerry Myerson May 6 '12 at 13:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.