Degrees of faithful irreducible representations of $\mathbb{Z}_n$ over finite fields I came across the following theorem while studying representation theory over finite fields.
A cyclic group $\mathbb{Z}_n$ has a faithful irreducible representation of degree $d$ over $\mathbb{F}_p$ if and only if $n \mid p^d-1$ but $n \not\mid p^i-1$ for all $i<d$
I can show that under these conditions a faithful irreducible representation of degree $d$ over $\mathbb{F}_p$ exists by sending a generator of the cyclic group to the companion matrix of a polynomial of degree $d$ in $\mathbb{F}_p[x]$. 
My question is 
a) How can I show that all faithful irreducible representations of degree $d$ can be found in this way.
b) How can I show that there are no faithful irreducible representation of other degrees.
Thank you very much in advance.
 A: A finite dimensional representation of a cyclic group $C_n$ in a $K$-vector space $V$ is determined up to isomorphism by (the conjugacy class of) the image $g\in GL(V)$ of a generator of the group. If the representation is irreducible then the minimal polynomial of $g$ must be irreducible (if it had a nontrivial proper divisor $P\in K[X]$ then $\ker(P(g))$ would be a proper sub-representation). Conversely an endomorphism$~\eta$ of a vector space$~V$ with irreducible minimal polynomial$~\mu$ has no non-trivial stable subspaces precisely when $\deg\mu=\dim V$, in other words when the minimal polynomial coincides with the characteristic polynomial (this follows from the classification of modules over the PID $K[X]$, but also elementarily because for any nonzero vector$~v$ the minimal polynomial$~P$ such that $P(\eta)(v)=0$ has$~P\mid\mu$, whence $P=\mu$ by irreducibility, and $\dim K[\eta](v)=\deg P=\dim V$, so $v$ is not containined in any proper stable subspace). The $K[X]$-module $V$ with $X$ acting as$~\eta$ is isomorphic to $K[X]/(\mu)$, with $X^i$ corresponding to $g^i(v)$ for $0\leq i<\deg\mu$; in this basis the matrix $X$ acts by the companion matrix of$~\mu$.
The minimal polynomial of the image$~g$ of a chosen generator of$~C_n$ must divide $X^n-1$. Therefore the isomorphism classes of irreducible representations of $C_n$ over$~K$ are given by the irreducible factors$~P_i$ of the polynomial $X^n-1$ in $K[X]$; the dimension of the representation is given by the degree of the factor$~P_i$. When $P_i$ does not divide $X^d-1$ for any divisor$~d$ of$~n$, which implies $P_i$ divides (the image in $K[X]$ of) the $n$-th cyclotomic polynomial, then the representation is faithful. The representation is isomorphic to the one on the field $K[X]/(P_i)$ given by multiplication by the image of$~X$, a primitive $n$-th root of unity.
All this holds over an arbitrary field$~K$. When $\def\Fp{\Bbb F_p}K=\Fp$, the irreducible polynomials of degree$~d$ (with the exception of $X$, if $d=1$) are precisely the irreducible factors of $X^{p^d-1}-1$ that do not divide $X^{p^i-1}-1$ for any $i<d$; these are the minimal polynomials of the elements of the extension field $\Bbb F_{p^d}$ that are not contained in any proper sub-field of it. The polynomial $X^n-1$ divides $X^{p^d-1}-1$ if and only if $n$ divides $p^d-1$. This does not happen at all when $p$ divides $n$; otherwise the smallest $d$ for which this happens is given by the multiplicative order of$~p$ in $(\Bbb Z/n\Bbb Z)^\times$. The irreducible faithful representation of $C_n$ over$~\Fp$ are all of that degree$~d$; there are $\phi(n)/d$ different such representations.
