[GAP Forum] Primitive n-th Root of Unity in Finite Fields

[Alexander Hulpke]

Dear GAP-Forum,

Alexandra Alecu asked:

> Anyway... my problem is (and it might be an easy one) how to find the
> primitive n-th root of unity in a finite field?
> I noticed that for the complex numbers I could use E(n), I need  
> something
> similar for a finite field.
>
> All I have at the moment is a way to find the primitive n-th root  
> of unity
> for the cases when n = p^m - 1 where p is a prime and m > 1. For  
> this I use
> the PrimitiveRoot(GF(p^m)) which returns the primitive root of the  
> finite
> field GF(p^m).

The easiest way to find such a root is as power of a primitive root  
in a suitable field (which you also need to find):

Given your prime p and n, find the smallest m such that n divides p^m-1:

m:=1;
while (p^m-1) mod n<>0 do
   m:=m+1;
od;


Then take the generator of the corresponding finite field (which has  
order p^m-1) and power it up to get a primitive root of order n:
a:=PrimitiveRoot(GF(p^m))^((p^m-1)/n);

Be aware that there are some limits on finite fields in GAP, e.g. you  
might not be able to do this for arbitrary large p or n.

Best wishes,

    Alexander Hulpke

-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke