DFT modulo $p$: how to find the primitive root $\omega_n$.

Question

On complex numbers:

Suppose that we want to find the DFT of the polynomial $A$ given in coefficient form

$$a = (a_0, ..., a_{n-1})$$

where $n$ is the length $a$.

What we do is to

1. Find the $n$th primitive root, defined as $\omega_n = e^{2\pi i/n}$.
2. Compute the Vandermonde matrix $V_n$.
3. Compute $y = \mathrm{DFT}(a) = V_n a$, where

$$y_k = \sum_{i=0}^{n-1}a_i\omega_n^{ki}$$

---

On $\mathrm{Z}_p$:

As I understand, when we want to find the DFT of $A \mod p$ ($p$ - prime) we (according to what I read here):

1. Find a generator $g$ of $\mathbb{Z}_{p}$.
2. Use $g$ to derive $\omega_n$ - the $n$th (principal) primitive root $\mod p$, which is defined by $\omega_n = g^k$, where $k$ comes from the equation $\varphi(p) = p-1 = k\cdot n$. If we found $k$ such that the latter equation takes place, then $\omega_n = g^k$ is indeed the $n$th principal root, because $\omega_n^n = g^{kn} = g^{p-1} = 1 \mod p$ (by Euler's Theorem).
3. Compute the Vandermonde matrix and $y = V_na$ with all operations $\mod p$.

---

Example

To calculate the DFT of $a = [6, 0, 10, 7, 2] \mod 11$ (length $n = 5$) we find that one of the generators of $\mathbb{Z}_{11}$ is $6$, which implies the primitive root $\omega_n = 6^k = 6^2 = 3 \mod 11$ (since $\varphi(11) = 10 = k\cdot 5 = 2\cdot 5$).

---

Question: How do I choose $k$ when $p < n$?

Let illustrate this:

To calculate the DFT of $a = [-4, 3, 0, 6] \mod 7$ (length $n = 4$) we find that one of the generators of $\mathbb{Z}_7$ is $3$. To derive $\omega_n$ I have to find a number $k$ such that $\varphi(7) = 7 = k\cdot n = k\cdot 4$, but there is no $k \in \mathbb{Z}^+$ that can give $7$ when multiplied by $4$ and I can't compute $\omega_n = g^k = 3^k \mod 7$.

To be precise, in that website they describe the procedure of computing the DFT modulo $p$, by defining first a working modulo $M$, such that

1. $1 \leq n < M$
2. Every element in $a$ is in the range $[0, M)$.

And then select an integer $k$ such that $p = kn + 1$, $p \geq M$ and $p$ - prime.

This kind of make sense to me if I'm the one choosing which $p$ to use. But what if that is not the case?