# Polynomials, finite fields and cardinality/dimension considerations

Can someone please give me a hint how to prove that the quotient ring $\mathbb{F}_p[x]/{\langle f\rangle}$, where $f$ is a irreducible polynomial of degree $k$ and $p$ is a prime (and $\langle f\rangle$ the ideal generated by $f$), has cardinality $p^k$ and how to determine the dimension of $\mathbb{F}_p[x]/{\langle f\rangle}$ as a vector space ?

-
I changed $<f>$ to $\langle f \rangle$. TeX is not limited to the character on the keyboard. –  Michael Hardy Nov 15 '11 at 18:58

Because $\mathbb{F}_p$ is a field, $\mathbb{F}_p[x]$ is a Euclidean domain.

So every element $q(x)\in \mathbb{F}_p[x]$ can be written as $$q(x) = p(x)f(x) + r(x),$$ where $r(x)=0$ or $\deg(r)\lt \deg(f)$.

That means that in $\mathbb{F}_p[x]/\langle f\rangle$, every polynomial is equivalent (equal up to a multiple of $f(x)$) with $0$ or a polynomial of degree strictly smaller than $\deg(f)$.

If $\deg(f)=k$, then the possible polynomials of degree smaller than $k$ are of the form $$a_0 + a_1x + \cdots + a_{k-1}x^{k-1},\quad a_i\in\mathbb{F}_p.$$ Simple counting gives you that the quotient has size at most $p^k$.

Now, if $$a_0+a_1x+\cdots+a_{k-1}x^{k-1} +\langle f\rangle = b_0+b_1x+\cdots + b_{k-1}x^{k_1}+\langle f\rangle,$$ then $f(x)$ divides $$(a_0 + \cdots +a_{k-1}x^{k-1})-(b_0+\cdots+b_{k-1}x^{k_1}) = (a_0-b_0)+\cdots + (a_{k-1}-b_{k-1})x^{k-1}.$$ Since this is either $0$ or of degree strictly smaller than $f(x)$, the only way this can be a multiple of $f(x)$ is if it is equal to $0$. So two distinct polynomials of degree less than $\deg(f)$ represent the same coset if and only if they are identical, which shows that $\mathbb{F}_p[x]$ has at least $p^k$ elements.

Putting the two together tells you the size is exactly $p^k$.

Once you know the cardinality, the dimension follows, because an $n$-dimensional vector space over $\mathbb{F}_p$ has size $p^n$ (same counting argument as for polynomials of degree at most $k-1$ above; in fact, what we did above was to show that the classes $x^i+\langle f\rangle$, $i=0,\ldots,k-1$, are a basis).

-
Great answer, thanks. Though I still have one thing, that is unclear to me: Where does the fact that $f$ is irreducible comes into play ? –  arila Nov 16 '11 at 10:23
@arila: It does not come into play when determining the dimension of vector space $\mathbb{F}_p[x]/\langle f\rangle$ over $\mathbb{F}_p$. It comes into play in showing that this quotient is in fact a field. –  Arturo Magidin Nov 16 '11 at 17:02

If a polynomial, e.g. $x^3 + 2x^2 - 5x + 7$, is to be identified with $0$, then $x^3$ gets reduced to $-(2x^2 - 5x + 7)$ and $x^4$ to $x\cdot x^3$, etc.---keep reducing until everything's a linear combination of $1$, $x$, and $x^2$. And similarly for higher degrees. That gives you the dimension of the vector space.

-
With a very small complication if the leading coefficient of your polynomial is not one. –  Gerry Myerson Nov 15 '11 at 22:31

Well, $\mathbb{F}_p/\langle f \rangle$ is a vector space over $\mathbb{F}_p$ (if that isn't immediately obvious, you should sit down and write down a proof to convince yourself). If we write

$f=a_0 + a_1 x + \cdots + a_n x^n$

with $a_i\in \mathbb{F}_p$, then you can use $f$ to find a basis for $\mathbb{F}_p/\langle f \rangle$ as a vector space over $\mathbb{F}_p$. (Hint: a potential basis is staring you right in the face.) That will tell you the dimension.

-