Irreducible representations of a cyclic group over a field of prime order Consider $G$ a cyclic group of order $n$ with prime $p\nmid n$.
How do I construct all the irreducible representations over $\mathbb F_p$?
How many irreducible representations are there and what are their dimensions?
 A: The group algebra $\mathbb{F}_p[G]$ is isomorphic to the ring
$$
\mathbb{F}_p[x]/\langle x^n-1\rangle
$$
(map the generator of $G$ to the coset of $x$).
The derivative of the polynomial $f(x)=x^n-1$ is $f'(x)=nx^{n-1}$.
As $\gcd(n,p)=1$, we see that $\gcd(f(x),f'(x))=1$, so $f(x)$ has no repeated zeros in any extension of $\mathbb{F}_p$. Therefore in the factorization (in $\mathbb{F}_p[x]$)
$$
f(x)=\prod_j f_j(x)
$$
to irreducible factors, all the factors $f_j(x)$ are distinct. By the Chinese remainder theorem we thus get an isomorphism of rings
$$
\mathbb{F}_p[G]\simeq\bigoplus_j\mathbb{F}_p[x]/\langle f_j(x)\rangle.
$$
The summands are all extension fields of $\mathbb{F}_p$, so 
they are also the components of the Wedderburn decomposition of the group algebra. Maschke's theorem already told us that $\mathbb{F}_p[G]$ is semisimple. Furthermore, they are in bijective correspondence with the non-isomorphic irreducible representations. The dimensions are thus equal to $\deg f_j$ for each index $j$. 
The roots of the factors $f_j$ are various roots of unity of order that is a factor of $n$.
As the Galois group of any finite extension of $\mathbb{F}_p$ is generated by the Frobenius automorphism $F:x\mapsto x^p$, it is actually easy to calculate the degrees of the factors $f_j(x)$ without finding them explicitly.
As an example let us consider the case $p=3$, $n=10$. Let $g$ be a primitive tenth root of unity in some extension field of $\mathbb{F}_3$. We see that its conjugates are then
$F(g)=g^3$, $F(g^3)=g^9$, $F(g^9)=g^{27}=g^7$. The list stops here, because $F(g^7)=g^{21}=g$. Therefore the minimal polynomial of $g$ is $(x-g)(x-g^3)(x-g^9)(x-g^7)$. In the same way we see that the minimal polynomial of $g^2$ is $(x-g^2)(x-g^6)(x-g^8)(x-g^4)$. The missing two root $g^0=1$ and $g^5=-1=2$ belong to the prime field, so their minimal polynomials are linear. We have seen that $x^{10}-1$ splits into a product of two linear and two quartic factors in $\mathbb{F}_3[x]$. Hence the irreducible representations of $C_{10}$ over $\mathbb{F}_3$ have dimensions 1,1,4 and 4 respectively.
The previous example generalizes to a study of the so called cyclotomic cosets.
Also observe that these representations are not absolutely irreducible. As soon as we extend the ground field to contain the appropriate roots of unity, the usual arguments showing that irreducible reps of abelian groups are 1-dimensional kicks in. This manifests itself also on the polynomial ring side: over a splitting field the polynomial $x^n-1$ splits into linear factors.
In the case $p=2$ the irreducible modules are an extremely well studied object in coding theory. Namely they are the minimal cyclic codes of length $n$.

Oh, an answer is missing! Define a relation $\sim_p$ in $\mathbb{Z}_n$ as follows: $a\sim_p b$ if and only if $ap^k\equiv b\pmod{n}$ for some non-negative integer $k$. This is an equivalence relation (the equivalence classes are the cyclotomic cosets modulo $n$). The number of irreducible representations of $C_n$ over $\mathbb{F}_p$ is equal to the number of equivalence classes $[a]$ of the relation $\sim_p$, and their dimensions are equal to the number of elements $|[a]|$ of the corresponding equivalence class.
