Counting Primitive Roots in Finite Fields without Group Theory

[devious_]

I have the definition that if F is a finite field then a \in F is a primitive root if ord(a) = |F|-1.

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

(Note: This material is supposed not to use any group theory.)

 

[devious_]

I guess I'll just stick to the group theoretic proof.

 

[matt grime]

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.

 

[devious_]

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.

 

[mathwonk]

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.

 

[devious_]

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.

 

[matt grime]

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

The definition of primitive is that it generates: what else is it defined as?

 

[devious_]

The original post has the definition I was given.

 

[matt grime]

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.

 

[mathwonk]

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 let's 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? 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.)

 

[devious_]

Interesting final words.