Finding the qth root of unity mod p I have $p$ and $q$ as $p = 4916335901, q = 88903$ and I have to find the $q^{th}$ root of unity $\pmod{p} $, so its $q{th}$ root of unity $\pmod{4916335901}$.
What exactly is a $q^{th}$ root and what would it be for this? I have used this wiki page to try and help me calculate what it would be but can't seem to figure it out.
 A: A $q$th root of unity (generally in a field $K$), is any element $x \in K$ such that $x^q = 1$. A first thing to note is that $1$ is always a $q$th root of unity for any $q$ in any field $K$. So a first obvious answer to your question is that $1$ is a $q$th root of unity in the field $K = \mathbf{F}_{4916335901}$. 
But maybe you are looking for a primitive $q$th root of unity. A $q$th root of unity $x$ is primitive if $q$ is the smallest power of $x$ which equals $1$. In the case of finite fields, it is easy to tell whether a primitive $q$th roots of unity exists, and if so, to compute one.
Recall that if $K$ is a finite field with $p^r$ elements, then the multiplicative group $K^\times$ of non-zero elements in $K$ is cylic of order $p^r-1$. It is easy to see that $q$th roots of unity in $K$ form a subgroup of $K^\times$, which is noted $\mu_q(K)$, and moreover that if a primitive $q$th root of unity $x$ exists in $K$, $\mu_q(K)$ is cyclic of order $q$, and $x$ is a generator of $\mu_q(K)$.
It is known that a cyclic group of order $n$ has a subgroup of order $d$ if and only if $d$ divides $n$, so in the end, primitive $q$th roots of unity exist in $\mathbf{F}_{p^r}$ if and only if $q$ divides $p^r-1$. In your case, $q$ does indeed divide $p^r - 1 = 4916335900$, so primitive $q$th roots exist in $K$. Since also $q$ is prime, it is very easy to compute a primitive $q$th root of unity: take a random $x \in K^*$, and compute $y = x^{(p^r-1)/q}$. $y$ is obviously a $q$th root of unity, and it is primitive if and only if it is not $1$, because an element of a group of prime order is a generator if and only if it is not the identity.
