[GAP Forum] Primitive Root of Unity in Finite Fields

[Laurent Bartholdi]

Hi Alessandra!
> 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 guess here, and below, you mean *a* primitive root. In the complex
plane, there's a standard choice (thanks to the exponential map) but
in general there is not.

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

But this is quite general! to find a primitive n-th root of unity, you
find m such that p^m-1 is divisible by n; and you take
PrimitiveRoot(GF(p^m))^((p^m-1)/n).

In GAP code:
primroot := function(q,n) # returns a n-th primitive root in GF(q)
  local m;
  m := First([1..1000],m->RemInt(q^m,n)=1);
  return PrimitiveRoot(GF(q^m))^((q^m-1)/n);
end;

best, L
-- 
Laurent Bartholdi          \  laurent.bartholdi<at>gmail<dot>com
EPFL SB SMA IMB MAD         \    Téléphone: +41 21-6935458
Station 8                    \ Secrétaire: +41 21-6935471
CH-1015 Lausanne, Switzerland \      Fax: +41 21-6930339