Irreducible representations of $\mathbb{Z}/p\mathbb{Z}$ over Galois field $\mathbb{F}_q$, $p\neq q$. What is a sufficient condition for the existence of an irreducible representation of degree $n$ of the cyclic group of order $p$ over the field of $q$ elements when $p$ and $q$ are distinct primes?
Some obvious necessary conditions (for a non-trivial representation) are that $p$ must divide $\frac{q^n-1}{q-1}$ and $n \leq p$, but I have not been able to come up with a sufficient condition (apart from $n=1$).
The motivation is that such a representation gives rise (via the corresponding semidirect product) to a group, whose order is not the power of a prime, but such that the order of any proper subgroup is the power of a prime, and all such groups arise this way.
 A: A necessary and sufficient condition for the cyclic group of order p to have a faithful irreducible representation of dimension n over a field with q elements (where p is prime, q is a prime power, and n is a positive integer) is:

n is the multiplicative order of q mod p.

Equivalently,

p divides the value of the nth cyclotomic polynomial evaluated at q.

The cyclic group of order p has exactly p absolutely irreducible representations over an algebraically closed field of characteristic dividing q (assuming that p, q are relatively prime).  Each is of dimension one, and is parameterized by the eigenvalue of a generator of the cyclic group: a pth root of unity inside the algebraic closure of the field with q elements.
If the multiplicative order of q mod p is n, then the non-identity eigenvalues generate a field of order qn over the field of q elements.  Writing such eigenvalues as matrices over the field of q elements gives an irreducible (but only absolutely irreducible when n = 1) representation of dimension n.
For instance, when p is 7, then we have the following cases:


*

*0 ≡ q mod 7: one absolutely irreducible representation of degree 1

*1 ≡ q mod 7: seven absolutely irreducible representations of degree 1

*2 ≡ q mod 7: one absolutely irreducible representation of degree 1, two irreducible representations of degree 3

*3 ≡ q mod 7: one absolutely irreducible representation of degree 1, one irreducible representation of degree 6

*4 ≡ q mod 7: one absolutely irreducible representation of degree 1, two irreducible representations of degree 3

*5 ≡ q mod 7: one absolutely irreducible representation of degree 1, one irreducible representation of degree 6

*6 ≡ q mod 7: one absolutely irreducible representation of degree 1, three irreducible representations of degree 2



We can decompose the regular representation over the algebraic closure: it is just diagonal matrices with p distinct pth roots of unity as entries.  Over the field with q elements, we'd need the matrix entries to be stable under qth powers.
For instance, if 6 ≡ q mod 7, then we get:
$$\begin{bmatrix} \zeta_7^0 &.&.&.&.&.&.\\ .&\zeta_7^1&.&.&.&.&.\\ .&.&\zeta_7^{-1}&.&.&.&. \\ .&.&.&\zeta_7^2&.&.&. \\ .&.&.&.&\zeta_7^{-2}&.&. \\ .&.&.&.&.&\zeta_7^3&. \\ .&.&.&.&.&.&\zeta_7^{-3} \end{bmatrix}$$
is conjugate to
$$
\left[\begin{array}{r|rr|rr|rr}
1 &.&.&.&.&.&.\\ \hline
.&.&1&.&.&.&.\\ .&\zeta_7^1 + \zeta_7^{-1}&-1&.&.&.&. \\ \hline
.&.&.&.&1&.&. \\ .&.&.&\zeta_7^2+\zeta_7^{-2}&-1&.&. \\ \hline
.&.&.&.&.&.&1 \\ .&.&.&.&.&\zeta_7^3+\zeta_7^{-3}&-1 \end{array}\right]$$
and this matrix is unchanged by replacing its entries with their qth powers (which is a field automorphism in fields whose characteristic divides q).  Note how the eigenvalues get paired up, since 6 ≡ q mod 7 has multiplicative order 2.
For 2 ≡ q mod 7, they would get matched up in triples:
$$\begin{bmatrix} \zeta_7^0 &.&.&.&.&.&.\\ .&\zeta_7^1&.&.&.&.&.\\ .&.&\zeta_7^{2}&.&.&.&. \\ .&.&.&\zeta_7^4&.&.&. \\ .&.&.&.&\zeta_7^{-1}&.&. \\ .&.&.&.&.&\zeta_7^{-2}&. \\ .&.&.&.&.&.&\zeta_7^{-4} \end{bmatrix}$$
is conjugate to
$$
\left[\begin{array}{r|rrr|rrr}
1 &.&.&.&.&.&.\\ \hline
.&.&1&.&.&.&.\\ .&.&.&1&.&.&. \\ .&\omega&\omega^*&-1&.&.&. \\ \hline
.&.&.&.&.&1&. \\ .&.&.&.&.&.&1 \\ .&.&.&.&\omega^*&\omega&-1 \end{array}\right]$$
where $ \omega = \zeta_7^1 + \zeta_7^{2}+\zeta_7^4$ and $\omega^* = \zeta_7^{-1} + \zeta_7^{-2}+\zeta_7^{-4}$ are exchanged by "complex conjugation" but are fixed under the qth Frobenius map.
A: Here is a distinct answer that is more about the group theory.  It uses a small thing about simple modules over commutative rings.
Suppose G is a group in which every proper subgroup has prime power order.  This means in particular, that no proper p subgroup is normalized by any q element.  Assuming G is solvable, we get that Fit(G) = Oq(G) for some prime q, and that the Sylow p-subgroup P of G acts irreducibly on Fit(G). In particular, Fit(G) is an elementary abelian q-subgroup. Since P⋅Fit(G) is a subgroup not of prime power order, it must equal G, and so G is the semi-direct product of P and Fit(G).  If P had a non-identity proper subgroup R, then R⋅Fit(G) would be a proper subgroup not of prime power order, so P must have order p.
Now GF(q)[P] = GF(q)[x]/(xp−1) and so Fit(G) is a quotient of this commutative ring by a maximal ideal.  In particular, Fit(G) is an extension field of GF(q) generated as a vector space by the x-multiples of any non-identity element of Fit(G).  Call its dimension n.
In particular, x is not contained in any proper subfield of Fit(G) and so p cannot divide qd−1 for any d < n, including d = 1 as observed by Tobias.  Of course, p must divide qn−1 since it is an element of a field of order qn.  These conditions are exactly that n is the multiplicative order of q mod p.
