#+TITLE: Assignment Seven
#+AUTHOR: Lizzy Hunt
#+STARTUP: entitiespretty fold inlineimages
#+LATEX_HEADER: \notindent \notag \usepackage{ dsfont } \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
#+LATEX: \setlength\parindent{0pt}
#+OPTIONS: toc:nil


* Section 4.2
** Question Five
*** b
\begin{align*}
x^5 + x^4 + 2x^3 - x^2 - x - 2 &= (x - 1)(x^4 + 2x^3 + 5x^2 + 4x + 4) + (-x^3 - x + 2) \\
x^4 + 2x^3 + 5x^2 + 4x + 4 &= (-x-2)(-x^3 - x + 2) + (4x^2 + 4x + 8)\\
-x^3 - x + 2 &= (\frac{-x}{4})(4x^2 + 4x + 8) + 0
\end{align*}

$(4x^2 + 4x + 8) = 4(x^2 + x + 2)$

$x^2 + x + 2$
*** c
$deg(d) = 2$ is the greatest degree of a possible common divisor, so we'll stick with $x^2 - 1$.
*** g
\begin{align*}
2x^4 + 5x^3 - 5x - 2 &= (x + 4)(2x^3 - 3x^2 - 2x) + (14x^2 + 3x - 2) \\
2x^3 - 3x^2 - 2x &= (\frac{x}{7} - \frac{12}{49})(14x^2 + 3x - 2) + (\frac{-48x - 24}{49}) \\
14x^2 + 3x - 2 &= (\frac{-7x}{24})(\frac{-48x - 24}{49}) + 0
\end{align*}

$\frac{-48x - 24}{49} = \left(\frac{49}{-48}\right)\left(\frac{\left(-48x-24\right)}{49}\right) = x + \frac{1}{2}$

$x + \frac{1}{2}$
** Question Ten
$x^3 - 3abx + a^3 + b^3$ can be factored to $(a + b + x) (a^2 - a b - a x + b^2 - b x + x^2)$, so $a + b + x$ is the gcd.

* Section 4.3
** Question Three
*** a
{ $x^2 + x + 1$, $2x^2 + 2x + 2$, $3x^2 + 3x + 3$, $4x^2 + 4x + 4$ }
*** b
{ $3x + 2$, $6x + 4$, $2x + 6$, $5x + 1$, $x + 3$, $4x + 5$ }

** Question Six
Assume that $x^2 + 1$ is in fact reducible. Then, $x^2 + 1 = (ax + b)(cx + d)$. Thus, $ax \cdot cx = x^2 \Rightarrow ac = 1$, $axd + bcx = 0 \Rightarrow ad + bc = 0$, and $bd = 1$ with $a,b,c,d$ all being nonzero.

Then, $a = \frac{1}{c}$ and $d = \frac{1}{b}$, so $ad = -bc \Rightarrow \frac{1}{cb} = - bc$, which is impossible.

** Question Nine
*** a
$x^2 + x + 1$

*** b
$x^3 + x^2 + 1$ and $x^3 + x + 1$

** Question Ten
*** a
In $\mathds{Q}[x]$, no. In $\mathds{R}[x]$, yes: $x^2 - 3 = (x - \sqrt{3})(x + \sqrt{3})$.

*** b
Yes, in both fields: $x^2 + x - 2 = (x + 2)(x - 1)$

** Question Eleven
Assume that $x^3 - 3$ were reducible in $\mathds{Z}_7 [x]$. Then, there must be a monic factor of degree one, as
$x^3 - 3 = g(x)h(x) \Rightarrow deg(x^3 - 3) = deg(g(x)h(x)) \Rightarrow 3 = deg(g(x)) + deg(h(x))$ by Theorem 4.2, and either $deg(g(x))$ or $deg(h(x))$ must be one, with the other, two.

So, one of the factors must be of the form $x + a, a \in \mathds{Z}_7$. None such factor exists since polynomial division always returns a non-zero remainder:

$x \nmid x^3 - 3$, trivially.

$\frac{x^3 - 3}{x + 1}$ gives a remainder of $4$.

$\frac{x^3 - 3}{x + 2}$ gives a remainder of $-11 \equiv_7 3$.

$\frac{x^3 - 3}{x + 3}$ gives a remainder of $-30 \equiv_7 5$.

$\frac{x^3 - 3}{x + 4}$ gives a remainder of $-67 \equiv_7 3$.

$\frac{x^3 - 3}{x + 5}$ gives a remainder of $-128 \equiv_7 5$.

$\frac{x^3 - 3}{x + 6}$ gives a remainder of $-219 \equiv_7 5$.

** Question Twelve
In $\mathds{Q}[x]$, $x^4 - 4 = (x^2 - 2)(x^2 + 2)$

In $\mathds{R}[x]$, $x^4 - 4 = (x - \sqrt{2})(x + \sqrt{2})(x^2 + 2)$

In $\mathds{C}[x]$, $x^4 - 4 = (x - \sqrt{2})(x + \sqrt{2})(x - i \sqrt{2})(x + i \sqrt{2})$

** Question Fourteen
$x^2 + x \equiv_6 (x + 4)(x + 3)$

$x^2 + x \equiv_6 x(x + 1)$

* Section 4.4
** Question Two
*** c
By Theorem 4.15, the remainder is $f(-1) = 5$

** Question Three
*** c
If the remainder of $\frac{f(x)}{h(x)}$ is 0, then $h$ is a factor of $f$, so using
Theorem 4.15 we can find that $f(-2) = -55 \equiv_5 0$, so $h$ is indeed a factor.

** Question Four
*** b
We need to find k such that $f(-1) = 0 (mod 5)$

\begin{verbatim}
>>> f = lambda k,x: (x**4 + 2 * x**3 - 3 * x**2 + k * x + 1) % 5
>>> for i in range(5):
...   if f(i, -1) == 0:
...     print(i)
...
2
\end{verbatim}

$k=2$ works nicely!

** Question Seven
\begin{verbatim}
>>> set(filter(lambda x: (x**7 - x) % 7 == 0, range(7)))
{0, 1, 2, 3, 4, 5, 6}
\end{verbatim}

Shows that each element is a root, so the factoring is correct by the Factor Theorem.

** Question Eight
*** b
The polynomial is irreducible since its only roots are $\pm \sqrt{7} \notin \mathds{Q}$, by Corollary 4.19

*** d
\begin{verbatim}
>>> set(filter(lambda x: (2 * x**3 + x**2 + 2 * x + 2) % 5 == 0, range(5)))
set()
\end{verbatim}

It's irreducible since there are no roots in $\mathds{Z}_5$.

** Question Nine
\begin{verbatim}
>>> def find_irr_mon_polys(deg, mod):
...    z_s = range(mod)
...    polys = set()
...    for b in z_s:
...       for c z_s:
...          f_repr = f"x^2 + {b}x + {c}"
...          f = lambda x: (x**2 + b*x + c) % mod
...          if not any(map(lambda x: f(x) == 0, z_s)):
...              polys.add(f_repr)
...    return polys

>>> find_irr_mon_polys(2, 5)
\end{verbatim}

{ $x^2 + 0x + 2,
 x^2 + 0x + 3,
 x^2 + 1x + 1,
 x^2 + 1x + 2,
 x^2 + 2x + 3,
 x^2 + 2x + 4,
 x^2 + 3x + 3,
 x^2 + 3x + 4,
 x^2 + 4x + 1,
 x^2 + 4x + 2$ }
 
\begin{verbatim}
>>> find_irr_mon_polys(2, 3)
\end{verbatim}
{ $x^2 + 0x + 1, x^2 + 1x + 2, x^2 + 2x + 2$ }

** Question Thirteen
*** a
If $f(x) = cg(x)$ with $c \neq 0_F$, then $g(x) = c^{-1}f(x)$ and $f(x) = c^{-1}g(x)$. Then, $g(y) = 0_F \Leftrightarrow f(y) = 0_F$.
*** b
No, consider $f(x) = x$ and $g(x) = x^2$ in $\mathds{Z}$, then $f$ and $g$ share $0$ as their only root, but they are not associates.