Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Primitive roots

  1. Dec 16, 2005 #1
    I have the definition that if F is a finite field then a [itex]\in[/itex] F is a primitive root if ord(a) = |F|-1.

    Now what I don't understand is how exactly are there [itex]\phi(|F|-1)[/itex] primitive roots?

    (Note: This material is supposed not to use any group theory.)
     
  2. jcsd
  3. Dec 16, 2005 #2
    I guess I'll just stick to the group theoretic proof. :smile:
     
  4. Dec 16, 2005 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    If g is a primitive root and h is another primitive root then h=g^r for some r, and this is only possible if r is coprime to the order of the mult. group, and each such choice of r gives a distinct primitive root hence there are phi(|F|-1) of them.
     
  5. Dec 17, 2005 #4
    Does the one I cooked up also work?

    If g is a primitive root then the group of units U_n is cyclic, of order phi(n), and generated by g. Hence it is also generated by g^k if gcd(k, phi(n))=1. So the number of such primtive roots is phi(phi(n)). (Here I assumed |F|=n. And of course phi(|F|) = |F|-1, since the units of F are all of F\{0}.)

    Either way, they both use some group theory, whereas the (freshman) course I'm taking is not supposed to have any group thery in it. I remember that the prof quickly talked about the proof when he stated this result in class, but I can't seem to recall what he did exactly.
     
    Last edited: Dec 17, 2005
  6. Dec 17, 2005 #5

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    it uses the concept of gcd, which precedes group theory by some thousands of years, or so i guess.

    even in the exact form you give it, it uses only modular arithmetic, which as written up by gauss in his disquisitiones, foreshadows group theory.
     
  7. Dec 19, 2005 #6
    Yeah, but we aren't supposed to know what cyclic groups are, or that primitive roots generate the group of units (of a finite field).

    Now that I think about it actually, I think the professor didn't even give a real proof, but simply waved his hands and maybe showed that it's intuitively plausible. That would explain why I didn't write down the proof in my notes. I guess the only way to find out is to ask him.

    Thanks, btw.
     
  8. Dec 19, 2005 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper


    The definition of primitive is that it generates: what else is it defined as?
     
  9. Dec 19, 2005 #8
    The original post has the definition I was given.
     
  10. Dec 19, 2005 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    And that definition states that it is a generator: its order equals the order of the group. The only bit that is hard is showing that there is at least one generator: if we assume there is at least one then that there are exactly phi(|F|-1) of them is straight forward.
     
  11. Dec 19, 2005 #10

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    first, it would be nice to prove there exists at least one primitive root.
    so let F be finite field (how can a problem involving fields not use any group theory, when the very definition of a field is that it is a commutative, additive group, whose non zero elements form a commutative multiplicative group?)
    anyuway lets try to prove there is a non zero element of order equal to ord(F)-1.
    That would do it, since then it reduces to euclid's algorithm for finding the gcd of two integers.
    however this is not a trivial fact. let see, a primitive root is a root of the equation X^(q-1) - 1 = 0, where q = ord(F).
    now F is a field, so an equation of degree n has at most n roots.
    but since F is finite, the powers of a form a sequence with repetitions,
    say a^n = a^n+k. then i suppose we get immediately from the cancelation property of fields that a^k = 1. so every element of F-{0} has some finite order,
    and the order is obviously less than or equal to q-1. and only n elements can have order n by the remark above about the number of roots of an equation of degree n.
    so i guess we need to know that the order of every element divides q-1.
    well if not then let ord(a) = k and let p-i = kl + r with r < k.
    then we have ???.....5 or 10 minutes drunkenly later...
    how about these apples? (or grapes)
    every element of F-{0} has finite order, so let the distinct orders be a,b,c,...,d.
    then I claim:
    lemma 1) lcm(a,b,....d) = p-1.
    proof: every elements satisfies the equation X^r -1 = 0, where r = this lcm.
    hence since an equation of degree r can have only r roots, r is at least as large as q-1.
    but if r > q-1, then probably the product of one element of every order would be an element of order r > q-1, a contradiction, since every element has order at most q-1.
    now if this is correct, we are done.
    i.e. now the product of one elements of each order actually has order equal to q-1, which is hence a primitive root.
    now that one primitive root exists, we can easily see from the euclidean algorithm, or whatever, that there are exactly phi(q-1) such.
    i.e. the multiplicative set of non zero elements is of the same structure as the additive set Z/(q-1)Z, which has phi(q-1) units, hence F-{0} has phi(q-1) primitive roots.
    was denkst du???:tongue2: its a longgg day man. but i could not resist making my point that this elementary problem uses only the thousand year old ides of gcd and lcm (which are equaivalent ideas.)
     
    Last edited: Dec 19, 2005
  12. Dec 20, 2005 #11
    Interesting final words. :tongue2:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Primitive roots
  1. Primitive roots (Replies: 5)

  2. Primitive roots. (Replies: 3)

  3. Primitive root ! (Replies: 2)

Loading...