% 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 16, 2023 13:29:40}
%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}

\subsection{Problem}

How many semesters (or quarters) of abstract algebra have you taken (include
Galois theory, representation theory, group theory)?

\subsection{Solution sketch}

I've gotten answers ranging from $1$ to $5$.

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

\section{Exercise 2}

\subsection{Problem}

How familiar are you with the notions of

\begin{enumerate}
\item ring;

\item normal subgroup of a group;

\item Jordan canonical form (aka Jordan normal form) of a matrix;

\item quotient vector space $V/W$;

\item exact sequence;

\item determinant;

\item Cayley--Hamilton theorem;

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

\item complex number;

\item Gaussian integer;

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

\item discrete Fourier transform?
\end{enumerate}

(Write in a number between $0$ (for ``never seen it'') and $5$ (for ``remember
the important properties and could recall their proofs in 15 minutes without
looking up'') for each one.)

\subsection{Solution sketch}

Here are the answers I got, with some comments of mine:

\begin{enumerate}
\item ring: 4, 0, 5, 3, 4, 5, 3, 3, 3, 5, 5, 1.

Some spread here (but hopefully not so much any more now).

\item normal subgroup of a group: 3, 3, 3, 3, 4, 2, 2, 3, 2, 5, 5, 2.

I asked this one to assess how much you remembered of group theory. I don't
actually think normal subgroups will appear in this course (except in the
trivial sense: every subgroup of an abelian group is normal).

\item Jordan canonical form (aka Jordan normal form) of a matrix: 4, 5, 5, 5,
5, 4, 4, 3, 3, 5, 5, 4.

Nice! This should make the rational canonical form (which is a generalization
of the Jordan normal form to fields that are not algebraically closed) much
less mysterious.

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

Had you done your undergrad in Germany, you would have seen it in your first
semester :)

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: 1, 2, 0, 0, 2, 0, 1, 0, 1, 4, 1, 0.

If exact sequences are to appear in this course (and that's an
\textquotedblleft if\textquotedblright), it will be the short ones only. Their
proper habitat is courses on homological algebra and algebraic topology.

\item determinant: 5, 5, 5, 5, 5, 5, 4, 4, 4, 5, 5, 5.

Reassuring!

\item Cayley--Hamilton theorem: 4, 4, 5, 4, 5, 4, 4, 1, 3, 5, 5, 4.

I don't expect anyone to remember the proof -- at least not the algebraic one.

\item greatest common divisor of two (univariate) polynomials: 4, 1, 3, 4, 3,
4, 4, 4, 5, 5, 2, 3.

This will come useful to us pretty soon.

\item complex number: 5, 3.5, 5, 4, 5, 5, 4, 4, 4, 5, 5, 4.

Very nice.

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

Should be more now. The Gaussian integers are one of the nicest rings around
as far as good properties are concerned, and we'll soon see how they can be used.

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

There are conflicting definitions of a \textquotedblleft primitive $n$-th root
of unity\textquotedblright\ in the literature. The one I prefer (alas, not the
one in Dummit and Foote) is the following: A \textit{primitive }$n$\textit{-th
root of unity} in a field 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.

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

Not sure if I'll get there in this course, but it is a nice application of the
$n$-th roots of unity.
\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}$.

\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 \textit{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). However,
Kronecker found an algorithm for factoring polynomials in any number of
variables over $\mathbb{Z}$. A brief outline of the algorithm can be found in
\url{https://math.stackexchange.com/a/3127648/} , 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}

%----------------------------------------------------------------------------------------
%	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 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).

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

\section{Exercise 6}

\subsection{Problem}

You are given a $4 \times4$-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|}\hline
1 & 0 & 0 & 1\\\hline
1 & 1 & 0 & 0\\\hline
1 & 0 & 0 & 1\\\hline
0 & 1 & 1 & 1\\\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|}\hline
\textbf{0} & \textbf{1} & \textbf{1} & 1\\\hline
1 & \textbf{0} & 0 & 0\\\hline
1 & 0 & 0 & 1\\\hline
0 & 1 & 1 & 1\\\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 (albeit with a $5 \times5$-grid) on
\url{https://codepen.io/wintlu/pen/ZJJLGz} .]

\subsection{Solution sketch}

This is easier than I thought -- four moves suffice:%
\[%
\begin{tabular}
[c]{|c|c|c|c|}\hline
0 & 0 & 0 & 0\\\hline
0 & 0 & 0 & 0\\\hline
0 & 0 & 0 & 0\\\hline
0 & 0 & 0 & 0\\\hline
\end{tabular}
\ \rightarrow\
\begin{tabular}
[c]{|c|c|c|c|}\hline
\textbf{1} & \textbf{1} & \textbf{1} & 0\\\hline
0 & \textbf{1} & 0 & 0\\\hline
0 & 0 & 0 & 0\\\hline
0 & 0 & 0 & 0\\\hline
\end{tabular}
\ \rightarrow\
\begin{tabular}
[c]{|c|c|c|c|}\hline
1 & 1 & 1 & 0\\\hline
\textbf{1} & 1 & 0 & 0\\\hline
\textbf{1} & \textbf{1} & 0 & 0\\\hline
\textbf{1} & 0 & 0 & 0\\\hline
\end{tabular}
\ \rightarrow\
\begin{tabular}
[c]{|c|c|c|c|}\hline
1 & 1 & 1 & \textbf{1}\\\hline
1 & 1 & \textbf{1} & \textbf{1}\\\hline
1 & 1 & 0 & \textbf{1}\\\hline
1 & 0 & 0 & 0\\\hline
\end{tabular}
\ \rightarrow\
\begin{tabular}
[c]{|c|c|c|c|}\hline
1 & 1 & 1 & 1\\\hline
1 & 1 & 1 & 1\\\hline
1 & 1 & \textbf{1} & 1\\\hline
1 & \textbf{1} & \textbf{1} & \textbf{1}\\\hline
\end{tabular}
\ \ .
\]


The case of a $5\times5$-grid is much less obvious, but the answer is still
that 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, although many of you probably know them already.)

%----------------------------------------------------------------------------------------
%	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}

A \emph{conic} means a curve of the form
\[
\left\{  \left(  x, y \right)  \in\mathbb{R}^{2} \mid ax^{2} + bxy + cy^{2} +
dx + ey + f = 0 \right\}  ,
\]
where $a, b, c, d, e, f$ are six real numbers such that $\left(  a, b, c, d,
e, f \right)  \neq\left(  0, 0, 0, 0, 0, 0 \right)  $. Examples of conics are

\begin{itemize}
\item any circle, e.g., the unit circle $\left\{  \left(  x, y \right)
\in\mathbb{R}^{2} \mid x^{2} + y^{2} = 1 \right\}  $;

\item more generally, any ellipse;

\item any parabola, e.g., $\left\{  \left(  x, y \right)  \in\mathbb{R}^{2}
\mid x^{2} + y = 0 \right\}  $;

\item any hyperbola, e.g., $\left\{  \left(  x, y \right)  \in\mathbb{R}^{2}
\mid xy = 1 \right\}  $ or $\left\{  \left(  x, y \right)  \in\mathbb{R}^{2}
\mid x^{2} - y^{2} = 1 \right\}  $;

\item the union of any two lines, e.g., $\left\{  \left(  x, y \right)
\in\mathbb{R}^{2} \mid xy = 0 \right\}  $.
\end{itemize}

\noindent A conic is said to be \emph{nondegenerate} if it is not the union of
two lines.

\begin{itemize}
\item[\textbf{(a)}] What is the maximum number of points in which a
nondegenerate conic can intersect a line?

\item[\textbf{(b)}] What is the maximum number of points in which two
nondegenerate conics can intersect each other?
\end{itemize}

\subsection{Solution sketch}

\textbf{(a)} The maximum number is $2$.

\textit{Proof idea.} It is easy to see that the value $2$ can be achieved
(just pick the unit circle as the conic, and the x-axis as the line). It thus
remains to prove that a nondegenerate conic always intersects a line in at
most $2$ points.

Indeed, we observe that any invertible affine coordinate transformation (i.e.,
any invertible coordinate transformation of the form $\left(  x,y\right)
\mapsto\left(  \alpha x+\beta y+\gamma,\delta x+\varepsilon y+\varphi\right)
$, where $\alpha,\beta,\gamma,\delta,\varepsilon,\varphi$ are constants) sends
a conic to a conic\footnote{This is easy to see from the definition of a
conic: Essentially, a conic is the set of points at which a given nonzero
degree-$2$ polynomial vanishes. But an affine coordinate transformation sends
a degree-$2$ polynomial to a degree-$2$ polynomial.}, and sends a line to a
line; thus, it sends a nondegenerate conic to a nondegenerate conic.

Now, consider a nondegenerate conic $C$ and a line $L$. We must prove that $C$
intersects $L$ in at most $2$ points.

Indeed, we can always find an invertible affine coordinate transformation that
transforms $L$ into the x-axis (in fact, we can even find a congruence
transformation with this property). This transformation will transform the
nondegenerate conic $C$ into a new nondegenerate conic $C^{\prime}$. In order
to prove that $C$ intersects $L$ in at most $2$ points, it thus suffices to
show that $C^{\prime}$ intersects the x-axis in at most $2$ points.

Let the nondegenerate conic $C^{\prime}$ be given by the equation $P\left(
x,y\right)  =0$, where the polynomial $P\left(  x,y\right)  $ is
$ax^{2}+bxy+cy^{2}+dx+ey+f$. Then, the intersections of $C^{\prime}$ with the
x-axis are the points $\left(  0,y\right)  $ with $cy^{2}+ey+f=0$. Thus, we
see that there are at most $2$ such points unless $c=e=f=0$ (since a nonzero
quadratic equation has at most $2$ solutions). But the case $c=e=f$ cannot
occur, because in this case the polynomial $P\left(  x,y\right)  $ would
simplify to $P\left(  x,y\right)  =ax^{2}+bxy+dx=x\left(  ax+by+d\right)  $,
which would entail that the conic $C^{\prime}$ is degenerate (in fact,
$C^{\prime}$ is the union of the x-axis with the line with equation
$ax+by+d=0$ in this case). Hence, we conclude that $C^{\prime}$ intersects the
x-axis in at most $2$ points. Consequently, undoing our coordinate
transformation, we conclude that $C$ intersects $L$ in at most $2$ points.
This completes the proof.

\bigskip

\textbf{(b)} To be pedantic, the answer is $\infty$, since you can take two
identical nondegenerate conics.

Let's now answer the real question: What is the maximum number of points in
which two \textbf{distinct} nondegenerate conics can intersect each other?

I claim that this maximum number is $4$.

\begin{comment}
\textit{Incomplete proof idea.} It is easy to see that the value $4$ can be
achieved (just pick the unit circle and the hyperbola $xy=\dfrac{12}{25}$ as
the two conics\footnote{Their points of intersection are $\left(  \dfrac{4}%
{5},\dfrac{3}{5}\right)  $, $\left(  \dfrac{3}{5},\dfrac{4}{5}\right)  $,
$\left(  \dfrac{-4}{5},\dfrac{-3}{5}\right)  $ and $\left(  \dfrac{-3}%
{5},\dfrac{-4}{5}\right)  $. This example is courtesy of the Pythagorean
triangle with sides $3,4,5$.}). Thus, it remains to show that two distinct
nondegenerate conics always intersect in at most $4$ points.
Let
\begin{align*}
C  &  =\left\{  \left(  x,y\right)  \in\mathbb{R}^{2}\mid ax^{2}%
+bxy+cy^{2}+dx+ey+f=0\right\}  \ \ \ \ \ \ \ \ \ \ \text{and}\\
C^{\prime}  &  =\left\{  \left(  x,y\right)  \in\mathbb{R}^{2}\mid a^{\prime
}x^{2}+b^{\prime}xy+c^{\prime}y^{2}+d^{\prime}x+e^{\prime}y+f^{\prime
}=0\right\}
\end{align*}
be two distinct nondegenerate conics. We must show that $C$ and $C^{\prime}$
intersect in at most $4$ points.
Indeed, let $\left(  x,y\right)  $ be a point at which $C$ and $C^{\prime}$
intersect. Then,
\begin{align*}
ax^{2}+bxy+cy^{2}+dx+ey+f &  =0\ \ \ \ \ \ \ \ \ \ \text{and}\\
a^{\prime}x^{2}+b^{\prime}xy+c^{\prime}y^{2}+d^{\prime}x+e^{\prime}%
y+f^{\prime} &  =0.
\end{align*}
By taking an appropriate linear combination of these two equalities (e.g.,
$a^{\prime}$ times the first equality minus $a$ times the second, if $a$ and
$a^{\prime}$ are not both zero), we obtain a new equality%
\[
b^{\prime\prime}xy+c^{\prime\prime}y^{2}+d^{\prime\prime}x+e^{\prime\prime
}y+f^{\prime\prime}=0
\]
whose coefficients $b^{\prime\prime},c^{\prime\prime},d^{\prime\prime
},e^{\prime\prime},f^{\prime\prime}$ are not all $0$ (this is where we use
that $C$ and $C^{\prime}$ are distinct) and uniquely determined by
$a,b,c,d,e,f,a^{\prime},b^{\prime},c^{\prime},d^{\prime},e^{\prime},f^{\prime
}$ (independent on $x$ and $y$). This equality can be rewritten as%
\[
\left(  b^{\prime\prime}y+d^{\prime\prime}\right)  x+\left(  c^{\prime\prime
}y^{2}+e^{\prime\prime}y+f^{\prime\prime}\right)  =0.
\]
Solving this for $x$, we obtain%
\[
x=\dfrac{-\left(  c^{\prime\prime}y^{2}+e^{\prime\prime}y+f^{\prime\prime
}\right)  }{b^{\prime\prime}y+d^{\prime\prime}},
\]
unless both $b^{\prime\prime}y+d^{\prime\prime}$ and $c^{\prime\prime}%
y^{2}+e^{\prime\prime}y+f^{\prime\prime}$ are $0$. Assuming that
$b^{\prime\prime}y+d^{\prime\prime}$ and $c^{\prime\prime}y^{2}+e^{\prime
\prime}y+f^{\prime\prime}$ are not both $0$, we can use this equality to
uniquely determine $x$ if $y$ is known. Furthermore, plugging this equality
back into $ax^{2}+bxy+cy^{2}+dx+ey+f=0$, we obtain%
\[
a\left(  \dfrac{-\left(  c^{\prime\prime}y^{2}+e^{\prime\prime}y+f^{\prime
\prime}\right)  }{b^{\prime\prime}y+d^{\prime\prime}}\right)  ^{2}%
+b\dfrac{-\left(  c^{\prime\prime}y^{2}+e^{\prime\prime}y+f^{\prime\prime
}\right)  }{b^{\prime\prime}y+d^{\prime\prime}}y+cy^{2}+d\dfrac{-\left(
c^{\prime\prime}y^{2}+e^{\prime\prime}y+f^{\prime\prime}\right)  }%
{b^{\prime\prime}y+d^{\prime\prime}}+ey+f=0,
\]
which (upon clearing denominator) becomes a degree-$4$ equation in $y$. If
this equation is not trivial, it thus yields at most $4$ solutions for $y$.
Hence, we have at most $4$ solutions for $\left(  x,y\right)  $ (since each
$y$ yields a unique $x$).
This all relies on some nondegeneracy assumptions: We used that $b^{\prime
\prime}y+d^{\prime\prime}$ and $c^{\prime\prime}y^{2}+e^{\prime\prime
}y+f^{\prime\prime}$ are not both $0$, and that the resulting equation for $y$
is not trivial. Some more work is needed to ensure that this is actually the
case. It might not be true right away, but will be true after a coordinate transformation.
\bigskip
Assume the contrary. Thus, there are two nondegenerate conics%
\begin{align*}
&  \left\{  \left(  x,y\right)  \in\mathbb{R}^{2}\mid ax^{2}+bxy+cy^{2}%
+dx+ey+f=0\right\}  \ \ \ \ \ \ \ \ \ \ \text{and}\\
&  \left\{  \left(  x,y\right)  \in\mathbb{R}^{2}\mid a^{\prime}%
x^{2}+b^{\prime}xy+c^{\prime}y^{2}+d^{\prime}x+e^{\prime}y+f^{\prime
}=0\right\}
\end{align*}
that have at least $5$ distinct points $\left(  x_{1},y_{1}\right)  $,
$\left(  x_{2},y_{2}\right)  $, $\left(  x_{3},y_{3}\right)  $, $\left(
x_{4},y_{4}\right)  $ and $\left(  x_{5},y_{5}\right)  $ in common. Consider
these two conics and these $5$ points.
Since these $5$ points lie on the two conics, we have%
\begin{align*}
ax_{i}^{2}+bx_{i}y_{i}+cy_{i}^{2}+dx_{i}+ey_{i}+f  &
=0\ \ \ \ \ \ \ \ \ \ \text{and}\\
a^{\prime}x_{i}^{2}+b^{\prime}x_{i}y_{i}+c^{\prime}y_{i}^{2}+d^{\prime}%
x_{i}+e^{\prime}y_{i}+f^{\prime}  &  =0
\end{align*}
for each $i\in\left\{  1,2,3,4,5\right\}  $. In other words, the $5\times
6$-matrix
\[
Z:=\left(
\begin{array}
[c]{cccccc}%
x_{1}^{2} & x_{1}y_{1} & y_{1}^{2} & x_{1} & y_{1} & 1\\
x_{2}^{2} & x_{2}y_{2} & y_{2}^{2} & x_{2} & y_{2} & 1\\
x_{3}^{2} & x_{3}y_{3} & y_{3}^{2} & x_{3} & y_{3} & 1\\
x_{4}^{2} & x_{4}y_{4} & y_{4}^{2} & x_{4} & y_{4} & 1\\
x_{5}^{2} & x_{5}y_{5} & y_{5}^{2} & x_{5} & y_{5} & 1
\end{array}
\right)
\]
has both vectors
\[
v:=\left(
\begin{array}
[c]{c}%
a\\
b\\
c\\
d\\
e\\
f
\end{array}
\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ v^{\prime}:=\left(
%
\begin{array}
[c]{c}%
a^{\prime}\\
b^{\prime}\\
c^{\prime}\\
d^{\prime}\\
e^{\prime}\\
f^{\prime}%
\end{array}
\right)
\]
in its kernel. Since these two vectors $v$ and $v^{\prime}$ are linearly
independent (because otherwise, the two conics would be identical), this
entails that the kernel of the $5\times6$-matrix $Z$ has dimension $\geq2$.
Thus, the rank-nullity theorem shows that $\operatorname*{rank}Z\leq6-2=4$.
Thus, any $5\times5$-minor of $Z$ (that is, any determinant of a $5\times
5$-submatrix of $Z$) must be $0$. Hence, in particular,
\end{comment}


I thought there would be a simple algebraic proof, but I cannot find it now!

\begin{comment}
(I do remember a geometric proof, which probably won't make much sense unless
you are familiar with plane projective geometry. First of all, we switch from
the real plane $\mathbb{R}^{2}$ to the complex plane $\mathbb{C}^{2}$, simply
by allowing complex numbers as coordinates. Note that this complex plane is
$4$-dimensional when considered as an $\mathbb{R}$-vector space, but we don't
consider it that way. Now, we extend our two conics to $\mathbb{C}^{2}$ by
using the same equations. I claim that they still won't have more than $4$
points of intersection. To prove this, I extend the conics to the complex
\textbf{projective} plane $\mathbb{CP}^{2}$, which contains a line at
infinity. By a projec
\end{comment}


\bigskip

\textit{Remark:} Both parts \textbf{(a)} and \textbf{(b)} of the problem are
particular cases of
\textit{\href{https://en.wikipedia.org/wiki/Bezouts_theorem}{\textit{B\'{e}zout's
theorem for algebraic curves in the plane}}}, which states that two algebraic
curves of degrees $p$ and $q$ (in $\mathbb{R}^{2}$, or in $\mathbb{C}^{2}$, or
more generally in the Cartesian plane $F^{2}$ defined over any field $F$)
intersect in at most $pq$ points unless they have a whole algebraic curve in common.

\rule{0pt}{0.3pt} \\[0.4cm]
\end{document}