Every nonzero element of a finite field is a root of unity. Roots of unity behave very nicely, since the other roots of unity of the same order are just powers of the first.
For instance i is a primitive 4th root of unity, and the other one, -i, is just a power i,-1,-i,1.
The roots of unity form these nice cyclic subgroups of the group of units of a field.
If you want one primitive k'th root of unity, you get all of them for free, so we are just interested in the smallest finite field of characteristic p with a primitive k'th root of unity.
Now you get into trouble if p divides k: a finite field of characteristic p has size p^m, so its group of units has order p^m-1, and so k has to divide p^m-1. Such numbers are coprime to p.
In your question, you'll want to assume n is coprime to p, otherwise you won't get very good roots. For instance, when p=2, the 8th roots of unity are exactly {1}; none of them are primitive.
Groups of units of finite fields are very well behaved: they are all cyclic. So to find a primitive k'th root of unity, you just want to find the smallest m such that k divides p^m-1:
The field obtained by adjoining a primitive k=n(p-1)st root of unity is the field of size pm, where m is the order of p in the group of units of the ring Z / k Z.
Note that k has to be coprime to p in order for a primitive k'th root of unity to exist. Just divide k by p until it is coprime if you want to adjoin the "closest to primitive" root.