% Warning: The LaTeX code in this file is computer-generated.
% Do not expect to learn good LaTeX from it!

\documentclass[paper=a4, fontsize=12pt]{scrartcl}%
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathrsfs}
\usepackage{sectsty}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{framed}
\usepackage{ifthen}
\usepackage{lastpage}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage[all]{xy}
\usepackage{tikz}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, January 06, 2025 22:19:33}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\allsectionsfont{\centering \normalfont\scshape}
\usetikzlibrary{lindenmayersystems}
\setlength\parindent{20pt}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Iso}{\operatorname{Iso}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\SL}{\operatorname{SL}}
\newcommand{\Nil}{\operatorname{Nil}}
\newcommand{\Jac}{\operatorname{Jac}}
\newcommand{\Tor}{\operatorname{Tor}}
\newcommand{\Ext}{\operatorname{Ext}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\Coker}{\operatorname{Coker}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\mono}{\hookrightarrow}
\newcommand{\epi}{\twoheadrightarrow}
\newcommand{\iso}{\overset{\cong}{\to}}
\newcommand{\arinj}{\ar@{_{(}->}}
\newcommand{\arinjrev}{\ar@{^{(}->}}
\newcommand{\arsurj}{\ar@{->>}}
\newcommand{\arelem}{\ar@{|->}}
\newcommand{\arback}{\ar@{<-}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\newcommand{\myname}{Darij Grinberg}
\newcommand{\mymail}{darij.grinberg@drexel.edu}
\newcommand{\psetnumber}{0}
\ihead{Solutions to homework set \#\psetnumber}
\ohead{page \thepage\ of \pageref{LastPage}}
\ifoot{\myname}
\ofoot{\mymail}
\begin{document}

\title{ \normalfont {\normalsize \textsc{Drexel University, Department of
Mathematics} }\\[25pt] \rule{\linewidth}{0.5pt} \\[0.4cm] {\huge Math 533: Abstract Algebra I, }\\Winter 2021: Homework 0\\\rule{\linewidth}{2pt} \\[0.5cm] }
\author{Darij Grinberg}
\maketitle

%This command causes the title part to be printed.


%----------------------------------------------------------------------------------------
%	EXERCISE 1
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 1}

Omitted.

%----------------------------------------------------------------------------------------
%	EXERCISE 2
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 2}

\subsection{Problem}

How familiar are you with the notions of

\begin{enumerate}
\item normal subgroup of a group;

\item determinant;

\item ring;

\item Cayley--Hamilton theorem;

\item quotient vector space $V/W$;

\item exact sequence;

\item complex number;

\item Gaussian integer;

\item primitive $n$-th root of unity;

\item discrete Fourier transform?

\item greatest common divisor of two (univariate) polynomials;

\item tensor product;

\item cyclotomic polynomial;

\item Reed--Muller code;

\item Elkies--Stanley code;

\item Bose--Chaudhuri--Hocquenghem code?
\end{enumerate}

(Write in a number between $0$ (for ``never seen it'') and $5$ (for ``could
teach a lecture about it with no preparation'') for each one.)

\subsection{Solution sketch}

Here are the answers I got, with some comments of mine (modulo my data entry errors):

\begin{enumerate}
\item normal subgroup of a group: 4, 4, 4, 4, 3, 1, 5, 4, 4, 4, 5, 3.

Anyone with $\leq3$ on this should
\href{https://en.wikipedia.org/wiki/Normal_subgroup}{look this one up}, as we
will use this concept at least as a motivation. More importantly, we will use
the concept of a \textbf{quotient} of a group $G$ by a subgroup $H$. When $H$
is \textquotedblleft only\textquotedblright\ a subgroup of $G$, this quotient
(usually called $G/H$) is just a set with an action of $G$ on it. However,
when $H$ is a \textbf{normal} subgroup, this quotient $G/H$ also becomes a
group, i.e., we can define a multiplication on it by the rule $\overline
{g_{1}}\cdot\overline{g_{2}}:=\overline{g_{1}g_{2}}$ (or, to use more standard
notation, $g_{1}H\cdot g_{2}H:=g_{1}g_{2}H$) without running into ambiguities.

This is in Chapter 9 of Gallian's \textit{Contemporary Abstract Algebra} (10th
edition 2020), but he calls quotient groups \textquotedblleft factor
groups\textquotedblright.

The analogous concepts for rings are called \textquotedblleft
ideal\textquotedblright\ and \textquotedblleft quotient ring\textquotedblright%
, and will be two rather crucial concepts in this course.

\item determinant: 1, 4, 2, 4, 5, 5, 5, 4, 4, 5, 5, 3.

We won't use them much here, but they might come handy in some homework
exercises. Since you have seen group theory, I can define them quickly: Let
$A=\left(
\begin{array}
[c]{cccc}%
a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\
a_{2,1} & a_{2,2} & \cdots & a_{2,n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n,1} & a_{n,2} & \cdots & a_{n,n}%
\end{array}
\right)  \in R^{n\times n}$ be an $n\times n$-matrix with entries in a
commutative ring $R$. Then, its \textbf{determinant} $\det A$ is an element of
$R$, defined by the formula%
\[
\det A:=\sum_{\sigma\in S_{n}}\operatorname*{sign}\sigma\cdot
\underbrace{a_{1,\sigma\left(  1\right)  }a_{2,\sigma\left(  2\right)  }\cdots
a_{n,\sigma\left(  n\right)  }}_{=\prod_{i=1}^{n}a_{i,\sigma\left(  i\right)
}}.
\]
Here, $S_{n}$ is the $n$-th symmetric group (i.e., the group of all
permutations of $\left\{  1,2,\ldots,n\right\}  $), and $\operatorname*{sign}%
\sigma$ denotes the sign of a permutation $\sigma$ (which is $1$ if $\sigma$
is even, and $-1$ if $\sigma$ is odd; I called this $\left(  -1\right)
^{\sigma}$ \href{https://www.cip.ifi.lmu.de/~grinberg/t/22fco/}{back in Math
222}). You have likely seen and used determinants for matrices with real
entries; the case of entries in an arbitrary commutative ring $R$ is similar.
All their basic properties such as Laplace expansion, invariance under
row/column operations, etc. still hold for commutative rings\footnote{For
their proofs, see, e.g., Section 12 and Appendix B in: Neil Strickland,
\textit{MAS201 Linear Mathematics for Applications}, lecture notes, 28
September 2013. \url{https://neilstrickland.github.io/linear_maths/}
\par
Note that these proofs are stated for numbers, but work just as well in any
commutative ring.}. In particular, one can show that a square matrix $A\in
R^{n\times n}$ is invertible if and only if its determinant $\det A\in R$ is
invertible (in $R$). Determinants have lots of surprising applications; proofs
in algebraic combinatorics often boil down to equalities between certain determinants.

One reason why determinants are so useful in abstract algebra is that they
survive generalization to commutative rings better than other linear-algebraic
tools. A matrix with entries in an arbitrary $R$ cannot always be row-reduced
to a row echelon form, so Gaussian elimination doesn't work in general, but
determinants are still available.

\item ring: 1, 3, 2, 1, 0, 0, 3, 2, 2, 2, 4, 3.

Well, here's hoping the numbers will improve over time :)

\item Cayley--Hamilton theorem: 0, 0, 1, 0, 0, 0, 2, 3, 0, 0, 0, 3.

It's a beautiful result of linear algebra. It says that if you plug a square
matrix $A\in R^{n\times n}$ (again, $R$ can be any commutative ring) into its
own characteristic polynomial $\chi_{A}\left(  t\right)  =\det\left(
A-tI_{n}\right)  $, then you obtain the zero matrix. Here at Drexel, it is
probably Math 504 material (but usually only proved for $R=\mathbb{R}$ and
$R=\mathbb{C}$).

\item quotient vector space $V/W$: 0, 1, 0, 0, 0, 3, 0, 4, 1, 1, 0, 2.

Quotient vector spaces are \textquotedblleft like $\mathbb{Z}/n$ but for
vector spaces\textquotedblright. We'll soon learn about quotient rings and
quotient modules; quotient vector spaces are a particular case of the latter.

\item exact sequence: 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0.

We won't need them, but I was curious. They would appear at the very start of
a course on homological algebra (or midway through a first course in algebraic topology).

\item complex number: 4, 5, 3, 3, 9(?), 5, 5, 5, 4, 4, 5, 5.

Good to see some large numbers here; they will be a recurring example in our class.

\item Gaussian integer: 0, 1, 0, 0, 3, 0, 2, 0, 1, 1, 1, 0, 0, 4.

A \textbf{Gaussian integer} is a complex number $a+bi$ where both $a$ and $b$
are integers (as opposed to arbitrary real numbers). We will learn more about
them very soon.

\item primitive $n$-th root of unity: 0, 0, 0, 0, 0, 1, 0, 0, 3, 1, 0, 5.

For your culture: There are conflicting definitions of a \textquotedblleft
primitive $n$-th root of unity\textquotedblright\ in the literature. The one I
prefer is the following: A \textbf{primitive }$n$\textbf{-th root of unity} in
a field\footnote{Field = nontrivial commutative ring in which every nonzero
element has an inverse.} means an element $x$ of the field such that $x^{n}=1$
while the $n-1$ powers $x^{1},x^{2},\ldots,x^{n-1}$ are distinct from $1$. For
example, the imaginary unit $i$ of the field $\mathbb{C}$ is a primitive
$4$-th root of unity. More example, the primitive $n$-th roots in $\mathbb{C}$
are the numbers of the form $e^{2\pi ik/n}$, where $k\in\left\{
1,2,\ldots,n\right\}  $ is coprime to $n$. Primitive $n$-th roots of unity are
essential in number theory and applied mathematics, and directly related to
the ancient problem of constructing regular $n$-gons; but I'm not sure if
we'll see much of them in this course.

\item discrete Fourier transform: 0, 2, 1, 0, 0, 2, 0, 2, 1, 2, 3, 2.

I thought I might get to it as an application of primitive $n$-th roots of
unity. At this point, probably unlikely. You might learn about it somewhere
else, though.

\item greatest common divisor of two (univariate) polynomials: 1, 0, 0, 2, 0,
0, 0, 1, 2, 1, 2, 0.5.

OK, I had expected higher numbers here. I'll have to cover this in more detail
than I thought.

\item tensor product: 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 3.

Sadly, won't get there. Hugely important topic, but takes a couple weeks of acclimatization.

\item cyclotomic polynomial: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.

Another ship passing in the wind; it would fit well if we had another quarter.

\item Reed--Muller code: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.

I hope to get to this one. It's a nice application of polynomials over finite fields.

\item Elkies--Stanley code: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.

Good! This was a control question. Elkies and Stanley have both worked in
coding theory, but there is no such thing as an Elkies--Stanley code.

\item Bose--Chaudhuri--Hocquenghem code: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.

This one is not a control question; this code (or, rather, these codes -- it's
a whole class) \href{https://en.wikipedia.org/wiki/BCH_code}{exists}! Another
application of polynomials over finite fields, but too advanced to
realistically cover in Math 332.
\end{enumerate}

%----------------------------------------------------------------------------------------
%	EXERCISE 3
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 3}

\subsection{Problem}

\begin{itemize}
\item[\textbf{(a)}] Factor the polynomial $a^{3} + b^{3} + c^{3} - 3abc$.

\item[\textbf{(b)}] Factor the polynomial $bc\left(  b-c \right)  + ca\left(
c-a \right)  + ab\left(  a-b \right)  $.

\item[\textbf{(c)}] How general have your methods been? Did you use tricks
specific to the given polynomials, or do you have an algorithm for factoring
any polynomial (say, with integer coefficients)?
\end{itemize}

\subsection{Solution sketch}

\textbf{(a)} The answer is%
\[
a^{3}+b^{3}+c^{3}-3abc=\left(  a+b+c\right)  \left(  a^{2}+b^{2}%
+c^{2}-bc-ca-ab\right)  .
\]
This is if you want to factor the polynomial over $\mathbb{Z}$ (i.e., into
polynomials with integer coefficients). Over $\mathbb{C}$, you can factor it
further:%
\[
a^{3}+b^{3}+c^{3}-3abc=\left(  a+b+c\right)  \left(  a+\zeta b+\zeta
^{2}c\right)  \left(  a+\zeta^{2}b+\zeta c\right)  ,
\]
where $\zeta=e^{2\pi i/3}=\dfrac{-1+\sqrt{3}i}{2}$. (This $\zeta$ is a
primitive $3$-rd root of unity, by the way; the three complex numbers
$1,\zeta,\zeta^{2}$ are the vertices of an equilateral triangle when drawn in
the plane.)

\bigskip

\textbf{(b)} The answer is%
\[
bc\left(  b-c\right)  +ca\left(  c-a\right)  +ab\left(  a-b\right)  =\left(
a-b\right)  \left(  a-c\right)  \left(  b-c\right)  .
\]


\bigskip

\textbf{(c)} All of the above factorizations can be found using specialized tricks:

For instance, in part \textbf{(a)}, it helps to rewrite $a^{3}+b^{3}%
+c^{3}-3abc$ in terms of the three \textbf{elementary symmetric polynomials}
$e_{1}=a+b+c$, $e_{2}=ab+ac+bc$ and $e_{3}=abc$ (it is a famous result of
Gauss that any symmetric polynomial in $a,b,c$ can be expressed as a
polynomial in $e_{1},e_{2},e_{3}$, and there is an algorithm that finds such
an expression); once this is done, the $a+b+c$ factor immediately leaps to the
eye. The other factor, $a^{2}+b^{2}+c^{2}-bc-ca-ab$, is irreducible over
$\mathbb{Z}$ (you can check this easily by substituting distinct constants for
$b$ and $c$ and checking that the resulting quadratic in $a$ has no real
roots); over $\mathbb{C}$ you can factor it using the usual methods for
solving quadratic equations (treating $b$ and $c$ as constants).

I discussed ways of finding the factorization in \textbf{(b)} on
\url{https://math.stackexchange.com/a/3127648/} . The simplest one is to
observe that the polynomial vanishes for $b=c$ and therefore must be divisible
by $b-c$. (Do you see why?)

The more interesting question is how to factor polynomials in general. There
is no fully general algorithm for factoring polynomials over an arbitrary
field, even if the polynomials are univariate (see
\url{https://mathoverflow.net/a/350877/} for a brief outline of the reason
why). However, Kronecker found an algorithm for factoring polynomials in any
number of variables over $\mathbb{Z}$. This algorithm is outlined in \S 6.5 of
the notes, but you may want to find it yourself. It is based on the following
two ideas:

\begin{enumerate}
\item If $f\in\mathbb{Z}\left[  x\right]  $ is a polynomial in one variable
$x$ with integer coefficients, and if $g\in\mathbb{Z}\left[  x\right]  $ is a
polynomial that divides $f$ in $\mathbb{Z}\left[  x\right]  $, then the
integer $g\left(  n\right)  $ divides $f\left(  n\right)  $ for each
$n\in\mathbb{Z}$. Unless $f=0$, there are only finitely many $n\in\mathbb{Z}$
for which $f\left(  n\right)  =0$.

\item If $f\in\mathbb{Z}\left[  x_{1},x_{2},\ldots,x_{n}\right]  $ is a
polynomial in $n>1$ variables $x_{1},x_{2},\ldots,x_{n}$ with integer
coefficients, and if $g\in\mathbb{Z}\left[  x_{1},x_{2},\ldots,x_{n}\right]  $
is a polynomial that divides $f$, then the polynomial $g\left(  x_{1}%
,x_{2},\ldots,x_{n-1},x_{n-1}^{k}\right)  $ divides $f\left(  x_{1}%
,x_{2},\ldots,x_{n-1},x_{n-1}^{k}\right)  $ in the ring $\mathbb{Z}\left[
x_{1},x_{2},\ldots,x_{n-1}\right]  $ for any $k\in\mathbb{N}$. (Essentially,
this is saying that setting $x_{n}:=x_{n-1}^{k}$ does not break divisibility.)
Can you find a sufficiently high $k$ that ensures the converse also holds?
\end{enumerate}

This algorithm is mathematically bullet-proof but impractical due to the large
numbers that quickly appear. Nevertheless, for the above examples, it
shouldn't be too bad (with a modern computer). In practice, computer algebra
software uses more efficient algorithms, e.g., using the Chinese Remainder
Theorem (which we will see soon!) to \textquotedblleft
divide-and-conquer\textquotedblright\ the problem into several more manageable
(since small) problems.

%----------------------------------------------------------------------------------------
%	EXERCISE 4
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 4}

\subsection{Problem}

Simplify $\sqrt[3]{2 + \sqrt5} + \sqrt[3]{2 - \sqrt5}$.

\subsection{Solution sketch}

The answer is $1$.

You can find this numerically, but how to prove it?

\textit{First proof:} One way is to set $u=\sqrt[3]{2+\sqrt{5}}$ and
$v=\sqrt[3]{2-\sqrt{5}}$. We must then show that $u+v=1$. The definitions of
$u$ and $v$ yield $u^{3}=2+\sqrt{5}$ and $v^{3}=2-\sqrt{5}$, so that
$u^{3}+v^{3}=\left(  2+\sqrt{5}\right)  +\left(  2-\sqrt{5}\right)  =4$ and
$u^{3}v^{3}=\left(  2+\sqrt{5}\right)  \left(  2-\sqrt{5}\right)  =4-5=-1$.
Hence, $\left(  uv\right)  ^{3}=u^{3}v^{3}=-1$, so that $uv=-1$ (here we are
taking the cube root, which is unique because $u$ and $v$ are \textbf{real}
numbers). Now, the binomial formula yields%
\[
\left(  u+v\right)  ^{3}=u^{3}+3u^{2}v+3uv^{2}+v^{3}=\underbrace{u^{3}+v^{3}%
}_{=4}+\,3\underbrace{uv}_{=-1}\left(  u+v\right)  =4-3\left(  u+v\right)  .
\]


In other words, $u+v$ is a solution of the cubic equation $x^{3}=4-3x$. How do
you solve this cubic equation? If you try to apply
\href{https://en.wikipedia.org/wiki/Cubic_equation#Cardano's_formula}{Cardano's
formula}, you get right back to the expression $\sqrt[3]{2+\sqrt{5}}%
+\sqrt[3]{2-\sqrt{5}}$ you started with, which is not very useful. However, if
you already know what you are looking for (viz., you want to show that
$u+v=1$), you already \textbf{know} that $1$ is a root of the cubic
$x^{3}-\left(  4-3x\right)  $; polynomial division then shows that
$x^{3}-\left(  4-3x\right)  =\left(  x-1\right)  \left(  x+x^{2}+4\right)  $,
and this entails that $1$ is the \textbf{only} real root of this cubic (since
the factor $x+x^{2}+4$ has no real roots). In other words, $1$ is the only
real solution of the cubic equation $x^{3}=4-3x$. Since $u+v$ is a solution of
this equation, we thus conclude that $u+v=1$, qed.

\textit{Remark:} If you have no computer to tell you that the answer is
conspicuously close to $1$, you can still find it using
\href{https://en.wikipedia.org/wiki/Rational_root_theorem}{the rational root
test}, once you suspect that $u+v$ might be rational.

\bigskip

\textit{Second proof:} A straightforward computation shows that $\left(
\dfrac{1}{2}\left(  1+\sqrt{5}\right)  \right)  ^{3}=2+\sqrt{5}$. Thus,
$\sqrt[3]{2+\sqrt{5}}=\dfrac{1}{2}\left(  1+\sqrt{5}\right)  $. Similarly,
$\sqrt[3]{2-\sqrt{5}}=\dfrac{1}{2}\left(  1-\sqrt{5}\right)  $. Adding the
latter two equalities together yields $\sqrt[3]{2+\sqrt{5}}+\sqrt[3]%
{2-\sqrt{5}}=\dfrac{1}{2}\left(  1+\sqrt{5}\right)  +\dfrac{1}{2}\left(
1-\sqrt{5}\right)  =1$, qed.

\textit{Remark:} Guessing the identity $\left(  \dfrac{1}{2}\left(  1+\sqrt
{5}\right)  \right)  ^{3}=2+\sqrt{5}$ is far from straightforward, however!

%----------------------------------------------------------------------------------------
%	EXERCISE 5
%----------------------------------------------------------------------------------------
\rule{0pt}{0.3pt} \\[0.4cm]

\section{Exercise 5}

\subsection{Problem}

Let $n \in\mathbb{N}$. Let $a_{1}, a_{2}, \ldots, a_{n}$ be $n$ integers, and
let $b_{1}, b_{2}, \ldots, b_{n}$ be $n$ further integers. The Gaussian
elimination algorithm tells you how to solve the system
\begin{align*}
a_{1} x_{1} + a_{2} x_{2} + \cdots+ a_{n} x_{n}  &  = 0;\\
b_{1} x_{1} + b_{2} x_{2} + \cdots+ b_{n} x_{n}  &  = 0
\end{align*}
for $n$ unknowns $x_{1}, x_{2}, \ldots, x_{n} \in\mathbb{Q}$. The answer, in
general, will have the form ``all $\mathbb{Q}$-linear combinations (i.e.,
linear combinations with rational coefficients) of a certain bunch of
vectors''. (More precisely, ``a certain bunch of vectors'' are $n-2$ or $n-1$
or $n$ vectors with rational coordinates, depending on the rank of the $2
\times n$-matrix $%
\begin{pmatrix}
a_{1} & a_{2} & \cdots & a_{n}\\
b_{1} & b_{2} & \cdots & b_{n}%
\end{pmatrix}
$.)

Now, how can you solve the above system for $n$ unknowns $x_{1}, x_{2},
\ldots, x_{n} \in\mathbb{Z}$ ? Will the answer still be ``all $\mathbb{Z}%
$-linear combinations (i.e., linear combinations with integer coefficients) of
a certain bunch of vectors''?

What about more general systems of linear equations to be solved for integer unknowns?

\subsection{Solution sketch}

Yes, the answer will still be \textquotedblleft all $\mathbb{Z}$-linear
combinations (i.e., linear combinations with integer coefficients) of a
certain bunch of vectors\textquotedblright. We will see why after we have
introduced the Smith normal form (a variant of Gaussian elimination for PIDs
instead of fields). See Remark 7.1.15 in the notes for some details.

%----------------------------------------------------------------------------------------
%	EXERCISE 6
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 6}

\subsection{Problem}

You are given a $5 \times5$-grid of lamps, each of which is either on or off.
For example, writing $1$ for ``on'' and $0$ for ``off'', it may look as
follows:
\[%
\begin{tabular}
[c]{|c|c|c|c|c|}\hline
1 & 0 & 0 & 1 & 1\\\hline
1 & 1 & 0 & 0 & 1\\\hline
1 & 0 & 0 & 1 & 0\\\hline
0 & 1 & 1 & 1 & 1\\\hline
0 & 1 & 0 & 0 & 0\\\hline
\end{tabular}
\]
In a single move, you can toggle any lamp (i.e., turn it on if it was off, or
turn it off if it was on); however, this will also toggle every lamp adjacent
to it. (``Adjacent to it'' means ``having a grid edge in common with it'';
thus, a lamp will have $2$ or $3$ or $4$ adjacent lamps.) For example, if we
toggle the second lamp (from the left) in the topmost row in the above example
grid, then we obtain
\[%
\begin{tabular}
[c]{|c|c|c|c|c|}\hline
\textbf{1} & \textbf{0} & \textbf{0} & 1 & 1\\\hline
1 & \textbf{1} & 0 & 0 & 1\\\hline
1 & 0 & 0 & 1 & 0\\\hline
0 & 1 & 1 & 1 & 1\\\hline
0 & 1 & 0 & 0 & 0\\\hline
\end{tabular}
\]
(where the boldfaced numbers correspond to the lamps that have been affected
by the move).

Assume that all lamps are initially off. Can you (by a strategically chosen
sequence of moves) achieve a state in which all lamps are on?

[\textit{Remark:} You can play this game on
\url{https://codepen.io/wintlu/pen/ZJJLGz} .]

\subsection{Solution sketch}

The desired state can be achieved. The same holds for any $n\times m$-grid,
and more generally for any (finite undirected) graph grid. This is an
illustration of linear algebra over the finite field $\mathbb{Z}/2$ (that is,
linear algebra where the scalars are not real numbers but elements of
$\mathbb{Z}/2$). Indeed, a state of our grid can be viewed as a vector over
$\mathbb{Z}/2$ (that is, a vector with entries in $\mathbb{Z}/2$); then, a
move corresponds to the addition of a certain fixed vector to it. See \S 6.1.4
in \url{https://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf} for how to use
this model to solve the problem in general. (We'll learn the prerequisites for
that solution soon.)

See \url{https://en.wikipedia.org/wiki/Lights_Out_(game)} for more about the game.

%----------------------------------------------------------------------------------------
%	EXERCISE 7
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 7}

\subsection{Problem}

\begin{itemize}
\item[\textbf{(a)}] How many of the numbers $0, 1, \ldots, 6$ appear as
remainders of a perfect square divided by $7$ ?

\item[\textbf{(b)}] How many of the numbers $0, 1, \ldots, 13$ appear as
remainders of a perfect square divided by $14$ ?
\end{itemize}

What about replacing $7$ or $14$ by $n$? Can you do better than just squaring
them all?

[For example, $3$ of the numbers $0, 1, \ldots, 4$ appear as remainders of a
perfect square divided by $5$ -- namely, the three numbers $0, 1, 4$.]

\subsection{Solution sketch}

We will use the notation $u\%n$ for the remainder obtained when dividing an
integer $u$ by a positive integer $n$. For example, $16\%7=2$.

\bigskip

\textbf{(a)} The following table shows the remainders of some perfect squares
divided by $7$:%

\[%
\begin{tabular}
[c]{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$k$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$
& $12$ & $13$\\\hline
$k^{2}\%7$ & $0$ & $1$ & $4$ & $2$ & $2$ & $4$ & $1$ & $0$ & $1$ & $4$ & $2$ &
$2$ & $4$ & $1$\\\hline
\end{tabular}
\ \ .
\]
You see that these remainders repeat every $7$ columns, because $\left(
k+7\right)  ^{2}\%7=k^{2}\%7$ for every integer $k$ (this follows from
$\left(  k+7\right)  ^{2}\equiv k^{2}\operatorname{mod}7$, which in turn is a
consequence of $k+7\equiv k\operatorname{mod}7$). Thus, we only need to count
the remainders obtained from any $7$ consecutive integers -- for example, from
$0,1,\ldots,6$. There are $4$ of these remainders (namely, $0,1,2,4$).

\bigskip

\textbf{(b)} The following table shows the remainders of some perfect squares
divided by $14$:%

\[%
\begin{tabular}
[c]{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$k$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$
& $12$ & $13$\\\hline
$k^{2}\%14$ & $0$ & $1$ & $4$ & $9$ & $2$ & $11$ & $8$ & $7$ & $8$ & $11$ &
$2$ & $9$ & $4$ & $1$\\\hline
\end{tabular}
\ \ \ .
\]
As in part \textbf{(a)}, we see that there are $8$ of these remainders
(namely, $0,1,2,4,7,8,9,11$).

\textit{Remark:} We can simplify our counting by observing the symmetry
$\left(  14-k\right)  ^{2}\%14=k^{2}\%14$ for each integer $k$ (so it suffices
to only scan the first $8$ squares $0^{2},1^{2},\ldots,7^{2}$).

\bigskip

What about the general question: Given a positive integer $n$, how many of the
numbers $0,1,\ldots,n-1$ appear as remainders of a perfect square divided by
$n$ ? Here is an outline of a solution:

\begin{enumerate}
\item Rewrite the question as \textquotedblleft How many elements of the
finite ring $\mathbb{Z}/n$ are squares?\textquotedblright. (Here, a
\textit{square} means an element of the form $a^{2}$, where $a\in\mathbb{Z}/n$.)

\item Solve this question when $n=p^{i}$ for some prime $p$ and some
$i\in\mathbb{N}$. The answers will be different depending on whether $p$ is
$2$ or not.

\item Use the Chinese Remainder Theorem to solve the case of general $n$.
\end{enumerate}

Note that the answer will \textbf{not} always be $\left\lceil \dfrac{n+1}%
{2}\right\rceil $, although we got this answer in both parts \textbf{(a)} and
\textbf{(b)} of the problem.

%----------------------------------------------------------------------------------------
%	EXERCISE 8
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 8}

\subsection{Problem}

Solve the following system of equations:%
\begin{align*}
a^{2}+b+c  &  =1;\\
b^{2}+c+a  &  =1;\\
c^{2}+a+b  &  =1
\end{align*}
for three complex numbers $a,b,c$.

\subsection{Solution sketch}

Let $\left(  a,b,c\right)  $ be a solution. Subtracting the equations
$a^{2}+b+c=1$ and $b^{2}+c+a=1$ from one another, we obtain%
\[
a^{2}+b-b^{2}-a=0.
\]
The left hand side of this equation factors as $\left(  a-b\right)  \left(
a+b-1\right)  $; thus, we have
\[
\left(  a-b\right)  \left(  a+b-1\right)  =0.
\]
In other words,%
\[
a-b=0\text{ or }a+b-1=0.
\]
Similarly, we have%
\[
b-c=0\text{ or }b+c-1=0.
\]
Similarly, we have%
\[
c-a=0\text{ or }c+a-1=0.
\]


Thus, we are in one of the following eight cases:

\textit{Case 1:} We have $a-b=0$ and $b-c=0$ and $c-a=0$.

\textit{Case 2:} We have $a-b=0$ and $b-c=0$ and $c+a-1=0$.

\textit{Case 3:} We have $a-b=0$ and $b+c-1=0$ and $c-a=0$.

\textit{Case 4:} We have $a-b=0$ and $b+c-1=0$ and $c+a-1=0$.

\textit{Case 5:} We have $a+b-1=0$ and $b-c=0$ and $c-a=0$.

\textit{Case 6:} We have $a+b-1=0$ and $b-c=0$ and $c+a-1=0$.

\textit{Case 7:} We have $a+b-1=0$ and $b+c-1=0$ and $c-a=0$.

\textit{Case 8:} We have $a+b-1=0$ and $b+c-1=0$ and $c+a-1=0$.

In each of the eight cases, we are left with a system of $3$ linear equations
in $3$ unknowns, which we can solve. Here are the details:

In Case 1, the system of linear equations yields $a=b=c$. Hence, in our
original equation $a^{2}+b+c=1$, we can replace all three unknowns by $c$.
Thus, we obtain $c^{2}+c+c=1$. This is a quadratic equation in $c$, and its
solutions are $\sqrt{2}-1$ and $-\sqrt{2}-1$. Hence, we obtain the solutions%
\begin{align*}
\left(  a,b,c\right)   &  =\left(  \sqrt{2}-1,\ \sqrt{2}-1,\ \sqrt
{2}-1\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \\
\left(  a,b,c\right)   &  =\left(  -\sqrt{2}-1,\ -\sqrt{2}-1,\ -\sqrt
{2}-1\right)  .
\end{align*}
Check that these two solutions are indeed solutions of the original system!

In Case 2, the system of linear equations yields $\left(  a,b,c\right)
=\left(  \dfrac{1}{2},\dfrac{1}{2},\dfrac{1}{2}\right)  $. However, this does
not satisfy the original equation $a^{2}+b+c=1$. Hence, we do not get any
solution in Case 2.

Case 3, too, does not contribute any solutions.

In Case 4, the system of linear equations yields $a=1-c$ and $b=1-c$. Hence,
in our original equation $a^{2}+b+c=1$, we can replace the unknowns $a$ and
$b$ by $1-c$. Thus, we obtain $\left(  1-c\right)  ^{2}+\left(  1-c\right)
+c=1$. This is a quadratic equation in $c$, and its solution is $1$. Thus,
$c=1$ and therefore $a=1-c=1-1=0$ and similarly $b=0$. Hence, we obtain the
solution%
\[
\left(  a,b,c\right)  =\left(  0,0,1\right)  .
\]
Again, check that this satisfies the original system!

Case 5 does not contribute any solutions.

Cases 6 and 7 contribute the solutions%
\[
\left(  a,b,c\right)  =\left(  1,0,0\right)  \ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \left(  a,b,c\right)  =\left(  0,1,0\right)  ,
\]
respectively.

Finally, Case 8 contributes the fake solution $\left(  a,b,c\right)  =\left(
\dfrac{1}{2},\dfrac{1}{2},\dfrac{1}{2}\right)  $ (in the sense that the linear
equations yield this solution, but it fails to satisfy the original system).

Thus, altogether, our system has the five solutions%
\begin{align*}
&  \left(  \sqrt{2}-1,\ \sqrt{2}-1,\ \sqrt{2}-1\right)
,\ \ \ \ \ \ \ \ \ \ \left(  -\sqrt{2}-1,\ -\sqrt{2}-1,\ -\sqrt{2}-1\right)
,\\
&  \left(  1,0,0\right)  ,\ \ \ \ \ \ \ \ \ \ \left(  0,1,0\right)
,\ \ \ \ \ \ \ \ \ \ \left(  0,0,1\right)  .
\end{align*}


\bigskip

\textit{Remark:} Systems of polynomial equations in general can be rather hard
to solve. The one in this exercise was chosen to be susceptible to a simple
trick (as we have seen above); but wiggle one of the coefficients a little bit
(e.g., replacing one of the three $1$'s by a $2$), and the answer gets much
more complicated. The fact that all three equations are quadratic does not
save us: A \textbf{system} of quadratic equations can be as complicated as a
univariate equation of arbitrarily high degree.

There \textbf{is} a general way of solving systems of polynomial equations,
assuming that you can solve univariate polynomial equations. This is known as
\textit{elimination theory}, and can be done either using resultants or using
Gr\"{o}bner bases (which we should see near the end of the course). Note that
this is \textbf{not} what we have done in our above solution.

%----------------------------------------------------------------------------------------
%	EXERCISE 9
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 9}

\subsection{Problem}

The following triangular table shows the binomial coefficients $\dbinom{n}{m}$
for $n \in\left\{  0, 1, \ldots, 7 \right\}  $ and $m \in\left\{  0, 1,
\ldots, n \right\}  $:
\[
\hspace{-0.5pc} \begingroup
\setlength{\tabcolsep}{4pt}
%Default value: 6pt
\renewcommand{\arraystretch}{0.5}
%Default value: 1%
\begin{tabular}
[c]{ll|ccccccccccccccccc}%
\vphantom{$\overset{k=0}{\swarrow}$} &  & $\phantom{20}$ & $\phantom{20}$ &
$\phantom{20}$ & $\phantom{20}$ & $\phantom{20}$ & $\phantom{20}$ &  &  &  &
$\overset{k=0}{\swarrow}$ & $\phantom{20}$ & $\phantom{20}$ & $\phantom{20}$ &
$\phantom{20}$ & $\phantom{20}$ & $\phantom{20}$ & $\phantom{20}$\\
\vphantom{$\overset{k=0}{\swarrow}$}$n=0$ & $\rightarrow$ &  &  &  &  &  &  &
&  & $1$ &  & $\overset{k=1}{\swarrow}$ &  &  &  &  &  & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=1$ & $\rightarrow$ &  &  &  &  &  &  &
& $1$ &  & $1$ &  & $\overset{k=2}{\swarrow}$ &  &  &  &  & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=2$ & $\rightarrow$ &  &  &  &  &  &  &
$1$ &  & $2$ &  & $1$ &  & $\overset{k=3}{\swarrow}$ &  &  &  & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=3$ & $\rightarrow$ &  &  &  &  &  & $1$
&  & $3$ &  & $3$ &  & $1$ &  & $\overset{k=4}{\swarrow}$ &  &  & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=4$ & $\rightarrow$ &  &  &  &  & $1$ &
& $4$ &  & $6$ &  & $4$ &  & $1$ &  & $\overset{k=5}{\swarrow}$ &  & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=5$ & $\rightarrow$ &  &  &  & $1$ &  &
$5$ &  & $10$ &  & $10$ &  & $5$ &  & $1$ &  & $\overset{k=6}{\swarrow}$ & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=6$ & $\rightarrow$ &  &  & $1$ &  & $6$
&  & $15$ &  & $20$ &  & $15$ &  & $6$ &  & $1$ &  & $\overset{k=7}{\swarrow}%
$\\
\vphantom{$\overset{k=0}{\swarrow}$}$n=7$ & $\rightarrow$ &  & $1$ &  & $7$ &
& $21$ &  & $35$ &  & $35$ &  & $21$ &  & $7$ &  & $1$ &
\end{tabular}
\endgroup
\]
(This is part of what is known as \emph{Pascal's triangle}.)

Now, in this table, let us replace each even number by a $0$ and each odd
number by a $1$. We obtain
\[
\hspace{-0.5pc} \begingroup
\setlength{\tabcolsep}{4pt}
%Default value: 6pt
\renewcommand{\arraystretch}{0.5}
%Default value: 1%
\begin{tabular}
[c]{ll|ccccccccccccccccc}%
\vphantom{$\overset{k=0}{\swarrow}$} &  & $\phantom{20}$ & $\phantom{20}$ &
$\phantom{20}$ & $\phantom{20}$ & $\phantom{20}$ & $\phantom{20}$ &
$\phantom{20}$ & $\phantom{20}$ & $\phantom{20}$ & $\overset{k=0}{\swarrow}$ &
$\phantom{20}$ & $\phantom{20}$ & $\phantom{20}$ & $\phantom{20}$ &
$\phantom{20}$ & $\phantom{20}$ & $\phantom{20}$\\
\vphantom{$\overset{k=0}{\swarrow}$}$n=0$ & $\rightarrow$ &  &  &  &  &  &  &
&  & $1$ &  & $\overset{k=1}{\swarrow}$ &  &  &  &  &  & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=1$ & $\rightarrow$ &  &  &  &  &  &  &
& $1$ &  & $1$ &  & $\overset{k=2}{\swarrow}$ &  &  &  &  & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=2$ & $\rightarrow$ &  &  &  &  &  &  &
$1$ &  & $0$ &  & $1$ &  & $\overset{k=3}{\swarrow}$ &  &  &  & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=3$ & $\rightarrow$ &  &  &  &  &  & $1$
&  & $1$ &  & $1$ &  & $1$ &  & $\overset{k=4}{\swarrow}$ &  &  & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=4$ & $\rightarrow$ &  &  &  &  & $1$ &
& $0$ &  & $0$ &  & $0$ &  & $1$ &  & $\overset{k=5}{\swarrow}$ &  & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=5$ & $\rightarrow$ &  &  &  & $1$ &  &
$1$ &  & $0$ &  & $0$ &  & $1$ &  & $1$ &  & $\overset{k=6}{\swarrow}$ & \\
\vphantom{$\overset{k=0}{\swarrow}$}$n=6$ & $\rightarrow$ &  &  & $1$ &  & $0$
&  & $1$ &  & $0$ &  & $1$ &  & $0$ &  & $1$ &  & $\overset{k=7}{\swarrow}$\\
\vphantom{$\overset{k=0}{\swarrow}$}$n=7$ & $\rightarrow$ &  & $1$ &  & $1$ &
& $1$ &  & $1$ &  & $1$ &  & $1$ &  & $1$ &  & $1$ &
\end{tabular}
\endgroup
\]
This looks rather similar to the third evolutionary stage of
\href{https://en.wikipedia.org/wiki/Sierpinski triangle}{Sierpinski's
triangle}:
\[
\pgfdeclarelindenmayersystem{Sierpinski triangle}{
\symbol{X}{\pgflsystemdrawforward}
\symbol{Y}{\pgflsystemdrawforward}
\rule{X -> X-Y+X+Y-X}
\rule{Y -> YY}
} \tikzset{
l-system={step=2cm/(2^3), order=3, angle=-120}
} \begin{tikzpicture}
\fill [black] (0,0) -- ++(0:2) -- ++(120:2) -- cycle;
\draw [draw=none] (0,0) l-system [l-system={Sierpinski triangle, axiom=X},fill=white];
\end{tikzpicture}
\]
%This graphic is from https://tex.stackexchange.com/a/119604/ .
(Each $0$ in the above table corresponds to a white $\triangle$ triangle, and
each $1$ corresponds to a black $\blacktriangle$ triangle.)

Where does this similarity come from?

\subsection{Solution sketch}

See \url{http://larryriddle.agnesscott.org/ifs/siertri/Pascal.htm} . (Follow
the \textquotedblleft proof\textquotedblright\ link for the proof, and then
the \textquotedblleft proof\textquotedblright\ link from there to a proof of
Lucas's theorem if you want to know. Note that the proof of Lucas's theorem is
a beautiful illustration of the usefulness of working with polynomials modulo
$p$ -- i.e., of working modulo an ideal.)

\begin{comment}
The similarity comes from the following fact:
\begin{theorem}
\label{thm.binom.lucas2.sierpi}Let $n\in\mathbb{N}$, and let $a,b\in\left\{
0,1,\ldots,2^{n}-1\right\}  $. Then,%
\[
\dbinom{2^{n}+a}{b}\equiv\dbinom{a}{b}\operatorname{mod}%
2\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \dbinom{2^{n}+a}{2^{n}%
+b}\equiv\dbinom{a}{b}\operatorname{mod}2.
\]
\end{theorem}
Theorem \ref{thm.binom.lucas2.sierpi} shows that the first $2^{n}$ rows (i.e.,
rows $0,1,\ldots,2^{n}-1$) of the Pascal's \textquotedblleft
reduced\textquotedblright\ triangle (i.e., the triangle obtained from Pascal's
triangle when all even entries are replaced by $0$s and all odd entries are
replaced by $1$s) are repeated twice in the next $2^{n}$ rows (i.e., rows
$2^{n},2^{n}+1,\ldots,2^{n+1}-1$). Thus, going from the first $2^{n}$ rows to
the first $2^{n+1}$ rows
\end{comment}


%----------------------------------------------------------------------------------------
%	EXERCISE 10
%----------------------------------------------------------------------------------------
\rule{\linewidth}{0.3pt} \\[0.4cm]

\section{Exercise 10}

\subsection{Problem}

The number $\sqrt{2}$ is a root of the polynomial $x^{2} - 2$. The number
$\sqrt{3}$ is a root of the polynomial $x^{2} - 3$. Can you find a polynomial
with integer coefficients that has $\sqrt{2} + \sqrt{3}$ as a root?

Yes, I know about the zero polynomial. Find a better one!

\subsection{Solution sketch}

A better one is $x^{4}-10x^{2}+1$.

\begin{proof}
Let $a:=\sqrt{2}+\sqrt{3}$. Then, $a-\sqrt{2}=\sqrt{3}$, so that $\left(
a-\sqrt{2}\right)  ^{2}=3$. Hence, $3=\left(  a-\sqrt{2}\right)  ^{2}%
=a^{2}-2\sqrt{2}a+2$. This is equivalent to $a^{2}-1=2\sqrt{2}a$. Now squaring
this again, we find $\left(  a^{2}-1\right)  ^{2}=8a^{2}$. Expanding and
bringing everything onto the left hand side, we obtain $a^{4}-10a^{2}+1=0$.
This completes our proof.
\end{proof}


\bigskip

Incidentally, the polynomial $x^{4}-10x^{2}+1$ has four roots:%
\[
\sqrt{2}+\sqrt{3},\ \ \ \ \ \ \ \ \ \ \sqrt{2}-\sqrt{3}%
,\ \ \ \ \ \ \ \ \ \ -\sqrt{2}+\sqrt{3},\ \ \ \ \ \ \ \ \ \ -\sqrt{2}-\sqrt
{3}.
\]
So the three extra roots $\sqrt{2}-\sqrt{3}$, $-\sqrt{2}+\sqrt{3}$ and
$-\sqrt{2}-\sqrt{3}$ are \textquotedblleft free-riding\textquotedblright\ on
$\sqrt{2}+\sqrt{3}$. Why is this not surprising? Or is it?\footnote{Google
\textquotedblleft conjugate numbers\textquotedblright\ for the answer; but a
proper understanding of conjugate numbers would require understanding of
\textbf{Galois theory}.}

\bigskip

So far, so nice. But many questions suggest themselves:

\begin{enumerate}
\item Can we do any better than $x^{4}-10x^{2}+1$ ? That is, can we find a
smaller-degree polynomial with integer coefficients that still has $\sqrt
{2}+\sqrt{3}$ as a root?

\item Can we also find such a polynomial for $\sqrt{p}+\sqrt{q}$ where $p$ and
$q$ are arbitrary integers?

\item What about $\sqrt[3]{p}+\sqrt[5]{q}$ and more complicated numbers?
\end{enumerate}

These questions are not as easy to answer as the above problem. The answer to
Question 1 is \textquotedblleft no\textquotedblright, but I'm not sure how
easy this is to prove\footnote{Of course, if you can prove the above implicit
observation that a polynomial with integer coefficients that has $\sqrt
{2}+\sqrt{3}$ as a root must also have the three \textquotedblleft free
riders\textquotedblright\ $\sqrt{2}-\sqrt{3}$, $-\sqrt{2}+\sqrt{3}$ and
$-\sqrt{2}-\sqrt{3}$ as roots, then this is pretty clear!}. Question 2 is
fairly easy (just repeat the above proof with $p$ and $q$ instead of $2$ and
$3$). Question 3 is noticeably trickier, but nevertheless the answer is
positive (although the required polynomials are much more complicated). The
best answer for $\sqrt[u]{p}+\sqrt[v]{q}$ (where $p$ and $q$ are integers and
$u$ and $v$ are positive integers) is a polynomial of degree $uv$ which is
most explicitly described as the determinant of a certain complicated
matrix\footnote{The matrix in question is (depending on your method) either
the Sylvester matrix of the two polynomials $t^{v}-q$ and $\left(  x-t\right)
^{u}-p$ (in the indeterminate $t$ over the polynomial ring $\mathbb{Z}\left[
x\right]  $), or the Kronecker sum of the companion matrices of the two
polynomials $x^{u}-p$ and $x^{v}-q$. The first method requires some good
familiarity with determinants; the second relies on tensor products. I wish
there was something simpler!}. If you want something more elementary, try the
$u=2$ case (i.e., try finding a polynomial for $\sqrt{p}+\sqrt[v]{q}$).


\end{document}