2
$\begingroup$

Theorem (Fermat's little Theorem). If $p$ is a prime and $a \in \mathbb{Z}$ with $a \nmid p$ then $a^{p-1} \equiv 1 \mod p.$

Let $\mathbb{Z}/p\mathbb{Z}$ denote the multiplicative group of integers modulo $p.$ Let $k$ be the order of $a.$ Then $a^k \equiv 1 \mod p.$ By Lagrange's theorem, the order of the element $k$ divides the order of the group $|(\mathbb{Z}/p\mathbb{Z})^{\times}| = p-1$ (since the order of $a$ is equal to the subgroup generated by $a$) so $p -1 = kq$ for some $q \in \mathbb{Z}.$ Therefore $a^{p-1} \equiv a^{kq} \equiv (a^k)^q \equiv 1^q \equiv 1. \hspace{1mm} \Box $

(i) Prove that $x^2+1$ is irreducible over the integers $\operatorname{mod} 11$.

Since the degree of $x^2+1$ is equal to $2,$ it follows that $x^2+1$ is reducible $\Longleftrightarrow x^2+1$ has a root in the finite field $\mathbb{Z}/11\mathbb{Z}.$ Suppose to the contrary that a root $a \in \mathbb{Z}/11\mathbb{Z}$ exists. Then $a^2 +1 \equiv 0 \mod 11 \Longrightarrow a^2 \equiv - 1 \equiv 10 \mod 11.$ By considering the multiplicative group $(\mathbb{Z}/11\mathbb{Z})^{\times}$ and applying the above theorem, $a^{11-1} \equiv a^{10} \equiv 1 \mod 11$ but since $a^{10} \equiv (a^2)^5 \equiv (-1)^5 \equiv -1 \mod 11,$ we have reached a contradiction.

(ii) Prove that $x^2+x+4$ is irreducible over the integer $\operatorname{mod} 11.$

(Show that none of the $11$ elements in the finite field $\mathbb{Z}/11\mathbb{Z}$ are congruent to $0 \mod 11.$)

First question: Does the proof for $(i)$ work?

Second: What's a good trick to prove $(ii)$ without plugging in elements from the field explictly?

$\endgroup$
  • 1
    $\begingroup$ Notice that $x^2+x+4\equiv (x+6)^2+1\pmod{11}.$ And I think your proof for $(i)$ works just fine. $\endgroup$ – awllower Apr 28 '15 at 10:22
2
$\begingroup$

Yes, the proof of $(i)$ is correct (it is essentially half of the proof of Euler's Criterion).

For $(ii)$ note $\ x^2\!+\!x\!+\!4 \equiv x^2\!-\!\color{#c00}{10}x\!+\!4 \equiv (x^2\!-\!5)^2\!+\!1 \equiv X^2\!+\!1\,$ so $(i)$ applies.

Remark $\ $ We chose an even rep $\,\color{#c00}{-10\equiv 1}\,$ for the coefficient $\,b\,$ of $\,x^1\,$ (to complete the square). This trick works for any odd modulus since one of $\,b\equiv b\pm n\,$ is even, by $\,n\,$ odd.

$\endgroup$
4
$\begingroup$

(i) works fine. For (ii), complete the square in $\mathbf Z/11\mathbf Z$ (note $2^{-1}=6 =-5)$. You'll be brought back to case (i).

$\endgroup$
  • $\begingroup$ No need to invert $2$ since one can choose an even rep for the coeff of $\,x^1,\,$ see my answer. $\endgroup$ – Bill Dubuque Apr 28 '15 at 14:52
2
$\begingroup$

Your proof of (i) is sufficient.

For (2), you of course could check the $11-1 =10$ nontrivial elements of the field explicitly. Alternatively, the proof of the quadratic formula works over any field such that $2\neq 0$. So in particular, it works over $\mathbb{Z}/11\mathbb{Z}$.

Thus, check to see it is irreducible, it suffices (since it is degree 2) to show it has no roots using the quadratic formula. This is just checking whehter the discriminant $b^2-4ac$ is a square in this field or not.

$\endgroup$
  • $\begingroup$ @St Vincent: I don't agree with the replacement of equality with congruence symbol: my explanation happen in the set $\mathbf Z/11\mathbf Z$, not in $\mathbf Z$. That's why I can write $2^{-1}=6$. Congruence is for integers, not residue classes. $\endgroup$ – Bernard Apr 28 '15 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.