# Thread: Irreducible Monic Polynomials

1. ## Irreducible Monic Polynomials

The problem is:
Count the number of irreducible monic polynomials of degree 2 in (Z/13Z)[X]. Prove your answer.

What would be the best way to do this problem, or any tips?

2. Originally Posted by icecube
The problem is:
Count the number of irreducible monic polynomials of degree 2 in (Z/13Z)[X]. Prove your answer.

What would be the best way to do this problem, or any tips?

First, you're looking for beasts of the form $\displaystyle x^2+bx+c\,,\,b\,,\,c\in \mathbb{F}_{13}$

Second, a polynomial of degree 3 or less over any field is irreducible iff it has no roots in the field, so you want that the above quadratic's discriminant has no solution in our field, i.e. : you want that $\displaystyle \Delta:=b^2-4c$ is NOT a quadratic residue $\displaystyle \mod 13$.

Well now, just check what elements in $\displaystyle \mathbb{F}_{13}$ are not quadratic residues and count up all the possibilites for $\displaystyle a,b\in \mathbb{F}_{13}$ ...

For example, as $\displaystyle \left(\frac{5}{13}\right)=\left(\frac{3}{5}\right) =-1$, we get that 5 is not a quadratic residue mod 13 ==> every pair of elements $\displaystyle b,c\in \mathbb{F}_{13}\,\,\,s.t.\,\,\,b^2-4c=5$ in this field will yield an irreducible quadratic, for example:

** $\displaystyle b=0\Longrightarrow -4c=5\Longrightarrow 9c=5 \Longrightarrow c=3\cdot 5= 2\Longrightarrow x^2+2$ is one irreducible quadratic;

** $\displaystyle b=1\Longrightarrow 1-4c=5\Longrightarrow 4c=-4=9\Longrightarrow c=9\cdot 10=12\Longrightarrow$ the quadratic $\displaystyle x^2+x+12$ is irreducible...etc.

Of course, there is a formula, but I really don't remember it, though you can look for it in the books...

Tonio

3. Haha, thank you. We've only lightly touched on irreducible polynomials in class (definition and some examples), though he didn't define monic in class for us. Strange.
I'll take your approach and see if I can do it ^-^.

4. Originally Posted by tonio
For example, as $\displaystyle \left(\frac{5}{13}\right)=\left(\frac{3}{5}\right) =-1$, we get that 5 is not a quadratic residue mod 13 ==> every pair of elements $\displaystyle b,c\in \mathbb{F}_{13}\,\,\,s.t.\,\,\,b^2-4c=5$ in this field will yield an irreducible quadratic, for example:
(sorry about double posting)
I understand that the discriminant should not be a quadratic residue but I'm not understanding how you get from $\displaystyle \left(\frac{5}{13}\right)t o \left(\frac{3}{5}\right)$ to find that 5 is not a quadratic residue.
EDIT: I see. It's the Legendre Symbol. Unfortunately, it hasn't been covered yet in my class and isn't allowed to be used . I'll just find all the quadratic nonresidues by hand by finding all the quadratic residues.