\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{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=Wednesday, June 07, 2023 19:56:15}
%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{\calF}{\mathcal{F}}
\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{\op}{\operatorname{op}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\tildot}{\mathbin{\widetilde{\cdot}}}
\newcommand{\Coker}{\operatorname{Coker}}
\newcommand{\symd}{\mathbin{\bigtriangleup}}
\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{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\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}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{warning}[1][Warning]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{teachingnote}[1][Teaching note]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\NOEXPAND{\horrule}[1]{\rule{\linewidth}{#1}}
\NOEXPAND{\symd}{\mathbin{\bigtriangleup}}
\fi
\newcommand{\myname}{Darij Grinberg}
\newcommand{\mymail}{darij.grinberg@drexel.edu}
\newcommand{\psetnumber}{2}
\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} }\\[15pt] \rule{\linewidth}{0.5pt} \\[0.4cm] {\huge Math 533: Abstract Algebra I, }\\Winter 2021: Homework 2\\\rule{\linewidth}{2pt} \\[0.5cm] Version with solutions \rule{0pt}{2pt} \\[0.5cm] }
\author{Darij Grinberg}
\maketitle
\tableofcontents

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

\section{Exercise 1}

\subsection{Problem}

Let $R$ be a ring. Let $a$ be a nilpotent element of $R$. (Recall that
``nilpotent'' means that there exists some $n \in\mathbb{N}$ such that $a^{n}
= 0$.)

\begin{itemize}
\item[\textbf{(a)}] Prove that $1 - a \in R$ is a unit.

\item[\textbf{(b)}] Let $u \in R$ be a unit satisfying $ua = au$. Prove that
$u - a \in R$ is a unit.
\end{itemize}

[\textbf{Hint:} Treat the geometric series $\dfrac{1}{1-x} = 1+x+x^{2}+\cdots$
as an inspiration. Nilpotent elements of a ring are an algebraic analogue of
the infamous ``sufficiently small $\varepsilon> 0$'' from real analysis. In
particular, a nilpotent element $a$ can be substituted (for $x$) into any
formal power series $r_{0} + r_{1} x + r_{2} x^{2} + \cdots$, since the
resulting sum will have only finitely many addends distinct from $0$. (You
don't actually need to write any infinite sums in your solution, but they can
help you come up with the solution in the first place.)]

\subsection{Solution}

The element $a$ of $R$ is nilpotent. In other words, there exists some
$n\in\mathbb{N}$ such that $a^{n}=0$ (by the definition of \textquotedblleft
nilpotent\textquotedblright). Consider this $n$.

If $u$ and $v$ are two commuting elements\footnote{Recall that two elements
$u$ and $v$ of $R$ are said to \textit{commute} if $uv=vu$.} of $R$, then%
\begin{equation}
u^{m}v=vu^{m}\ \ \ \ \ \ \ \ \ \ \text{for each }m\in\mathbb{N}
\label{sol.ring.unit-nilp.vu**k}%
\end{equation}
and%
\begin{equation}
\left(  uv\right)  ^{m}=u^{m}v^{m}\ \ \ \ \ \ \ \ \ \ \text{for each }%
m\in\mathbb{N}. \label{sol.ring.unit-nilp.uv**m}%
\end{equation}
These are two known facts, which can both be proved by induction on $m$. For
the sake of completeness, let me show the proofs:

[\textit{Proof of (\ref{sol.ring.unit-nilp.vu**k}):} We induct on $m$:

\textit{Induction base:} Comparing $\underbrace{u^{0}}_{=1}v=1v=v$ with
$v\underbrace{u^{0}}_{=1}=v\cdot1=v$, we obtain $u^{0}v=vu^{0}$. In other
words, (\ref{sol.ring.unit-nilp.vu**k}) holds for $m=0$.

\textit{Induction step:} Let $k\in\mathbb{N}$. Assume that
(\ref{sol.ring.unit-nilp.vu**k}) holds for $m=k$. We must show that
(\ref{sol.ring.unit-nilp.vu**k}) holds for $m=k+1$.

We have assumed that (\ref{sol.ring.unit-nilp.vu**k}) holds for $m=k$. In
other words, $u^{k}v=vu^{k}$. On the other hand, $uv=vu$ (since $u$ and $v$
are commuting). Now, $\underbrace{u^{k+1}}_{=uu^{k}}v=u\underbrace{u^{k}%
v}_{=vu^{k}}=\underbrace{uv}_{=vu}u^{k}=v\underbrace{uu^{k}}_{=u^{k+1}%
}=vu^{k+1}$. In other words, (\ref{sol.ring.unit-nilp.vu**k}) holds for
$m=k+1$. This completes the induction step. Thus,
(\ref{sol.ring.unit-nilp.vu**k}) is proven.]

[\textit{Proof of (\ref{sol.ring.unit-nilp.uv**m}):} We induct on $m$:

\textit{Induction base:} Comparing $\left(  uv\right)  ^{0}=1$ with
$\underbrace{u^{0}}_{=1}\underbrace{v^{0}}_{=1}=1\cdot1=1$, we obtain $\left(
uv\right)  ^{0}=u^{0}v^{0}$. In other words, (\ref{sol.ring.unit-nilp.uv**m})
holds for $m=0$.

\textit{Induction step:} Let $k\in\mathbb{N}$. Assume that
(\ref{sol.ring.unit-nilp.uv**m}) holds for $m=k$. We must show that
(\ref{sol.ring.unit-nilp.uv**m}) holds for $m=k+1$.

We have assumed that (\ref{sol.ring.unit-nilp.uv**m}) holds for $m=k$. In
other words, $\left(  uv\right)  ^{k}=u^{k}v^{k}$. On the other hand,
$u^{k}v=vu^{k}$ (by (\ref{sol.ring.unit-nilp.vu**k}), applied to $m=k$). Now,
\[
\left(  uv\right)  ^{k+1}=\left(  uv\right)  \underbrace{\left(  uv\right)
^{k}}_{=u^{k}v^{k}}=\left(  uv\right)  u^{k}v^{k}=u\underbrace{vu^{k}%
}_{\substack{=u^{k}v\\\text{(since }u^{k}v=vu^{k}\text{)}}}v^{k}%
=\underbrace{uu^{k}}_{=u^{k+1}}\underbrace{vv^{k}}_{=v^{k+1}}=u^{k+1}v^{k+1}.
\]
In other words, (\ref{sol.ring.unit-nilp.uv**m}) holds for $m=k+1$. This
completes the induction step. Thus, (\ref{sol.ring.unit-nilp.uv**m}) is proven.]

Now, we can step to the solution of the exercise:

\bigskip

\textbf{(a)} Define $b\in R$ by $b=a^{0}+a^{1}+\cdots+a^{n-1}$. Then,%
\begin{align*}
\left(  1-a\right)  b  &  =\left(  1-a\right)  \left(  a^{0}+a^{1}%
+\cdots+a^{n-1}\right) \\
&  =\underbrace{\left(  a^{0}+a^{1}+\cdots+a^{n-1}\right)  }_{=\left(
a^{0}+a^{1}+\cdots+a^{n}\right)  -a^{n}}-\underbrace{a\left(  a^{0}%
+a^{1}+\cdots+a^{n-1}\right)  }_{\substack{=aa^{0}+aa^{1}+\cdots
+aa^{n-1}\\=a^{1}+a^{2}+\cdots+a^{n}\\=\left(  a^{0}+a^{1}+\cdots
+a^{n}\right)  -a^{0}}}\\
&  =\left(  \left(  a^{0}+a^{1}+\cdots+a^{n}\right)  -a^{n}\right)  -\left(
\left(  a^{0}+a^{1}+\cdots+a^{n}\right)  -a^{0}\right) \\
&  =\underbrace{a^{0}}_{=1}-\underbrace{a^{n}}_{=0}=1-0=1
\end{align*}
and%
\begin{align*}
b\left(  1-a\right)   &  =\left(  a^{0}+a^{1}+\cdots+a^{n-1}\right)  \left(
1-a\right) \\
&  =\underbrace{\left(  a^{0}+a^{1}+\cdots+a^{n-1}\right)  }_{=\left(
a^{0}+a^{1}+\cdots+a^{n}\right)  -a^{n}}-\underbrace{\left(  a^{0}%
+a^{1}+\cdots+a^{n-1}\right)  a}_{\substack{=a^{0}a+a^{1}a+\cdots
+a^{n-1}a\\=a^{1}+a^{2}+\cdots+a^{n}\\=\left(  a^{0}+a^{1}+\cdots
+a^{n}\right)  -a^{0}}}\\
&  =\left(  \left(  a^{0}+a^{1}+\cdots+a^{n}\right)  -a^{n}\right)  -\left(
\left(  a^{0}+a^{1}+\cdots+a^{n}\right)  -a^{0}\right) \\
&  =\underbrace{a^{0}}_{=1}-\underbrace{a^{n}}_{=0}=1-0=1.
\end{align*}
Combining these two equalities, we see that $b$ is an inverse to $1-a$ in $R$.
Hence, the element $1-a$ of $R$ has an inverse, i.e., is a unit of $R$. This
solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} The element $u$ is a unit of $R$, and thus has an inverse
$u^{-1}$. This inverse $u^{-1}$ satisfies $u^{-1}a=au^{-1}$ (this can be seen
by comparing $u^{-1}\underbrace{ua}_{=au}u^{-1}=u^{-1}a\underbrace{uu^{-1}%
}_{=1}=u^{-1}a$ with $\underbrace{u^{-1}u}_{=1}au^{-1}=au^{-1}$). In other
words, the two elements $u^{-1}$ and $a$ of $R$ are commuting. Hence,
(\ref{sol.ring.unit-nilp.uv**m}) (applied to $u^{-1}$, $a$ and $n$ instead of
$u$, $v$ and $m$) yields $\left(  u^{-1}a\right)  ^{n}=\left(  u^{-1}\right)
^{n}\underbrace{a^{n}}_{=0}=0$. Hence, the element $u^{-1}a$ of $R$ is
nilpotent. Thus, we can apply part \textbf{(a)} of this exercise to $u^{-1}a$
instead of $a$. As a result, we conclude that $1-u^{-1}a\in R$ is a unit.

Now, recall that the units of $R$ form a group under multiplication. Thus, the
product of any two units of $R$ is again a unit. Hence, the product $u\left(
1-u^{-1}a\right)  $ of $u$ and $1-u^{-1}a$ is a unit (since $u$ and
$1-u^{-1}a$ are units). In other words, $u-a$ is a unit (since $u\left(
1-u^{-1}a\right)  =u-\underbrace{uu^{-1}}_{=1}a=u-a$). This solves part
\textbf{(b)} of the exercise.

\subsection{Remark}

Our above solution carefully hides any traces of its origins, but they are
still not hard to see: The $a^{0}+a^{1}+\cdots+a^{n-1}$ in the solution of
part \textbf{(a)} is just the infinite sum $1+a+a^{2}+\cdots$ suggested by the
hint, rewritten as a finite sum because $a^{n}=0$ renders all but the first
$n$ of its terms equal to $0$.

The inverse of $u-a$ in part \textbf{(b)} of the exercise can also be written
explicitly: It is $u^{-1}\left(  \left(  u^{-1}a\right)  ^{0}+\left(
u^{-1}a\right)  ^{1}+\cdots+\left(  u^{-1}a\right)  ^{n-1}\right)  $.

The \textquotedblleft$ua=au$\textquotedblright\ condition in part \textbf{(b)}
cannot be dropped. For example, if $u$ and $a$ are the elements $\left(
\begin{array}
[c]{cc}%
0 & 1\\
1 & 0
\end{array}
\right)  $ and $\left(
\begin{array}
[c]{cc}%
0 & 1\\
0 & 0
\end{array}
\right)  $ of the matrix ring $\mathbb{Q}^{2\times2}$, then $u$ is a unit and
$a$ is nilpotent, but $u-a=\left(
\begin{array}
[c]{cc}%
0 & 0\\
1 & 0
\end{array}
\right)  $ is not invertible (i.e., not a unit of this matrix ring).

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

\section{Exercise 2}

\subsection{Problem}

Let $R$ be a ring. We define a new binary operation
$\mathbin{\widetilde{\cdot}}$ on $R$ by setting
\[
a \mathbin{\widetilde{\cdot}} b = ba \qquad\text{for all } a, b \in R .
\]
(Thus, $\mathbin{\widetilde{\cdot}}$ is the multiplication of $R$, but with
the arguments switched.)

\begin{enumerate}
\item[\textbf{(a)}] Prove that the set $R$, equipped with the addition $+$,
the multiplication $\mathbin{\widetilde{\cdot}}$, the zero $0_{R}$ and the
unity $1_{R}$, is a ring.
\end{enumerate}

\noindent This new ring is called the \textit{opposite ring} of $R$, and is
denoted by $R^{\operatorname{op}}$.

Note that the \textbf{sets} $R$ and $R^{\operatorname{op}}$ are identical (so
a map from $R$ to $R$ is the same as a map from $R$ to $R^{\operatorname{op}}%
$); but the \textbf{rings} $R$ and $R^{\operatorname{op}}$ are generally not
the same (so a ring morphism from $R$ to $R$ is not the same as a ring
morphism from $R$ to $R^{\operatorname{op}}$).

\begin{enumerate}
\item[\textbf{(b)}] Prove that the identity map $\operatorname{id} : R \to R$
is a ring isomorphism from $R$ to $R^{\operatorname{op}}$ if and only if $R$
is commutative.

\item[\textbf{(c)}] Now, assume that $R$ is the matrix ring $S^{n \times n}$
for some commutative ring $S$ and some $n \in\mathbb{N}$. Prove that the map
\[
R \to R^{\operatorname{op}}, \qquad A \mapsto A^{T}
\]
(where $A^{T}$, as usual, denotes the transpose of a matrix $A$) is a ring isomorphism.

\item[\textbf{(d)}] Forget about $S$, and let $R$ be an arbitrary ring again.
Let $M$ be a right $R$-module. Prove that $M$ becomes a left
$R^{\operatorname{op}}$-module if we define an action of $R^{\operatorname{op}%
}$ on $M$ by
\[
rm = mr \qquad\text{ for all $r \in R^{\operatorname{op}}$ and $m \in M$}.
\]
(Here, the left hand side is to be understood as the image of $\left(  r, m
\right)  $ under the new action of $R^{\operatorname{op}}$ on $M$, whereas the
right hand side is the image of $\left(  m, r \right)  $ under the original
action of $R$ on $M$.)
\end{enumerate}

[\textbf{Hint:} There are many straightforward axioms to check. Don't give too
many details; one sentence per axiom should suffice (e.g., in part
\textbf{(d)}, you can say ``left distributivity for the left
$R^{\operatorname{op}}$-module $M$ follows from right distributivity from the
right $R$-module $M$'', or even ``the distributivity axioms for the new module
boil down to the distributivity axioms for the old module''). In parts
\textbf{(a)}, \textbf{(b)} and \textbf{(d)}, you only have to check the axioms
that have to do with multiplication. In \textbf{(c)}, you can use basic
properties of transposes of matrices without proof, as long as you say clearly
which properties you are using. You will need to use the commutativity of $S$
in one place.]

\subsection{Remark}

Parts \textbf{(b)} and \textbf{(c)} of this exercise gives some examples of
rings $R$ that are isomorphic to their opposite rings $R^{\operatorname{op}}$.
See \url{https://mathoverflow.net/questions/64370/} for examples of rings that
are not.

\subsection{Solution}

We shall follow the PEMDAS convention for the order of operations, treating
the new multiplication $\left.  \widetilde{\cdot}\right.  $ as a
multiplicative operation. Thus, the expression \textquotedblleft$a\left.
\widetilde{\cdot}\right.  b+c\left.  \widetilde{\cdot}\right.  d$%
\textquotedblright\ will mean \textquotedblleft$\left(  a\left.
\widetilde{\cdot}\right.  b\right)  +\left(  c\left.  \widetilde{\cdot
}\right.  d\right)  $\textquotedblright\ rather than \textquotedblleft%
$a\left.  \widetilde{\cdot}\right.  \left(  b+c\right)  \left.
\widetilde{\cdot}\right.  d$\textquotedblright.

We are in the slightly confusing situation of having two different
\textquotedblleft multiplications\textquotedblright\ on one and the same set
$R$: the original multiplication $\cdot$ of the ring $R$, and the new
multiplication $\left.  \widetilde{\cdot}\right.  $ of the ring
$R^{\operatorname*{op}}$ (although we still have not shown that
$R^{\operatorname*{op}}$ is actually a ring). Let us agree that if $a,b\in R$,
then the notation \textquotedblleft$ab$\textquotedblright\ shall always mean
\textquotedblleft$a\cdot b$\textquotedblright\ (that is, the image of the pair
$\left(  a,b\right)  $ under the original multiplication $\cdot$, not under
the new multiplication $\left.  \widetilde{\cdot}\right.  $).

The original ring $R$ satisfies all the ring axioms (since it is a ring).
Thus, in particular, $\left(  R,+,0\right)  $ is an abelian group, and
$\left(  R,\cdot,1\right)  $ is a monoid.

\bigskip

\textbf{(a)} Clearly, the addition $+$ and the multiplication $\left.
\widetilde{\cdot}\right.  $ are binary operations on $R$, and the elements
$0_{R}$ and $1_{R}$ indeed belong to $R$. It remains to prove that these two
operations and these two elements make $R$ into a ring. In order to do so, we
need to verify the ring axioms. These axioms are the following:

\begin{itemize}
\item \textbf{Additive axioms:} The triple $\left(  R,+,0_{R}\right)  $ is an
abelian group.

\item \textbf{Multiplicative axioms:} The triple $\left(  R,\left.
\widetilde{\cdot}\right.  ,1_{R}\right)  $ is a monoid. This means,
specifically, that the following hold:

\begin{itemize}
\item \textbf{Associativity of multiplication:} We have $a\left.
\widetilde{\cdot}\right.  \left(  b\left.  \widetilde{\cdot}\right.  c\right)
=\left(  a\left.  \widetilde{\cdot}\right.  b\right)  \left.  \widetilde{\cdot
}\right.  c$ for all $a,b,c\in R$. (Of course, we \textbf{cannot} use
\textquotedblleft$ab$\textquotedblright\ as an abbreviation for
\textquotedblleft$a\left.  \widetilde{\cdot}\right.  b$\textquotedblright,
since \textquotedblleft$ab$\textquotedblright\ already stands for the
different product $a\cdot b$.)

\item \textbf{Neutrality of one:} We have $a\left.  \widetilde{\cdot}\right.
1_{R}=1_{R}\left.  \widetilde{\cdot}\right.  a=a$ for all $a\in R$.
\end{itemize}

\item \textbf{Annihilation:} We have $a\left.  \widetilde{\cdot}\right.
0_{R}=0_{R}\left.  \widetilde{\cdot}\right.  a=0_{R}$ for all $a\in R$.

\item \textbf{Distributivity:} We have%
\[
a\left.  \widetilde{\cdot}\right.  \left(  b+c\right)  =a\left.
\widetilde{\cdot}\right.  b+a\left.  \widetilde{\cdot}\right.
c\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \left(  a+b\right)  \left.
\widetilde{\cdot}\right.  c=a\left.  \widetilde{\cdot}\right.  c+b\left.
\widetilde{\cdot}\right.  c
\]
for all $a,b,c\in R$.
\end{itemize}

Some of these axioms are more obvious than others. In particular, the additive
axioms clearly hold, since we already know that $\left(  R,+,0\right)  $ is an
abelian group. Let us now prove the \textquotedblleft Associativity of
multiplication\textquotedblright\ axiom, and leave the rest to the reader
(since the arguments always follow the same pattern of rewriting the $\left.
\widetilde{\cdot}\right.  $-products in terms of $\cdot$-products and applying
the ring axioms for the original ring $R$).

[\textit{Proof of the \textquotedblleft Associativity of
multiplication\textquotedblright\ axiom:} Let $a,b,c\in R$. We must prove that
$a\left.  \widetilde{\cdot}\right.  \left(  b\left.  \widetilde{\cdot}\right.
c\right)  =\left(  a\left.  \widetilde{\cdot}\right.  b\right)  \left.
\widetilde{\cdot}\right.  c$.

The definition of the operation $\left.  \widetilde{\cdot}\right.  $ yields
$b\left.  \widetilde{\cdot}\right.  c=cb$ and $a\left.  \widetilde{\cdot
}\right.  b=ba$ and%
\begin{equation}
a\left.  \widetilde{\cdot}\right.  \left(  b\left.  \widetilde{\cdot}\right.
c\right)  =\underbrace{\left(  b\left.  \widetilde{\cdot}\right.  c\right)
}_{=cb}a=\left(  cb\right)  a \label{sol.ring.op.a.ass.1}%
\end{equation}
and%
\begin{equation}
\left(  a\left.  \widetilde{\cdot}\right.  b\right)  \left.  \widetilde{\cdot
}\right.  c=c\underbrace{\left(  a\left.  \widetilde{\cdot}\right.  b\right)
}_{=ba}=c\left(  ba\right)  . \label{sol.ring.op.a.ass.2}%
\end{equation}
But the original ring $R$ satisfies the \textquotedblleft Associativity of
multiplication\textquotedblright\ axiom (since it is a ring); thus, $\left(
cb\right)  a=c\left(  ba\right)  $. In other words, the right hand sides of
the two equalities \eqref{sol.ring.op.a.ass.1} and \eqref{sol.ring.op.a.ass.2}
are equal. Thus, their left hand sides are also equal. In other words,
$a\left.  \widetilde{\cdot}\right.  \left(  b\left.  \widetilde{\cdot}\right.
c\right)  =\left(  a\left.  \widetilde{\cdot}\right.  b\right)  \left.
\widetilde{\cdot}\right.  c$. Thus, the \textquotedblleft Associativity of
multiplication\textquotedblright\ axiom is proven.]

We have now shown that the set $R$, equipped with the addition $+$, the
multiplication $\left.  \widetilde{\cdot}\right.  $, the zero $0_{R}$ and the
unity $1_{R}$, satisfies all the ring axioms. Hence, it is a ring. This solves
part \textbf{(a)} of the problem.

\bigskip

\textbf{(b)} $\Longrightarrow:$ Assume that $\operatorname{id}:R\rightarrow R$
is a ring isomorphism from $R$ to $R^{\operatorname{op}}$. We must prove that
$R$ is commutative.

We have assumed that $\operatorname*{id}$ is a ring isomorphism from $R$ to
$R^{\operatorname{op}}$. Thus, in particular, $\operatorname*{id}$ is a ring
morphism from $R$ to $R^{\operatorname{op}}$.

Recall that if $U$ and $V$ are two rings, and if $f$ is a ring morphism from
$U$ to $V$, then%
\begin{equation}
f\left(  a\cdot b\right)  =f\left(  a\right)  \cdot f\left(  b\right)
\ \ \ \ \ \ \ \ \ \ \text{for all }a,b\in U. \label{sol.ring.op.b.fwd.1}%
\end{equation}
(Indeed, this is one of the four axioms in our definition of a ring morphism.)
But keep in mind that the two \textquotedblleft$\cdot$\textquotedblright%
\ signs in the equality \eqref{sol.ring.op.b.fwd.1} have different meanings:
The \textquotedblleft$\cdot$\textquotedblright\ sign on the left hand side
stands for the multiplication of the ring $U$, whereas the \textquotedblleft%
$\cdot$\textquotedblright\ sign on the right hand side stands for the
multiplication of the ring $V$. Thus, \eqref{sol.ring.op.b.fwd.1} (applied to
$U=R$, $V=R^{\operatorname*{op}}$ and $f=\operatorname*{id}$) yields%
\begin{equation}
\operatorname*{id}\left(  a\cdot b\right)  =\operatorname*{id}\left(
a\right)  \left.  \widetilde{\cdot}\right.  \operatorname*{id}\left(
b\right)  \ \ \ \ \ \ \ \ \ \ \text{for all }a,b\in R
\label{sol.ring.op.b.fwd.2}%
\end{equation}
(since $\operatorname*{id}$ is a ring morphism from $R$ to
$R^{\operatorname{op}}$, and since the multiplication of the ring $R$ is
denoted by \textquotedblleft$\cdot$\textquotedblright\ whereas the
multiplication of the ring $R^{\operatorname*{op}}$ is denoted by
\textquotedblleft$\left.  \widetilde{\cdot}\right.  $\textquotedblright).

Now, if $a,b\in R$, then%
\begin{align*}
ab  &  =a\cdot b=\operatorname*{id}\left(  a\cdot b\right)
=\underbrace{\operatorname*{id}\left(  a\right)  }_{=a}\left.
\widetilde{\cdot}\right.  \underbrace{\operatorname*{id}\left(  b\right)
}_{=b}\qquad\left(  \text{by \eqref{sol.ring.op.b.fwd.2}}\right) \\
&  =a\left.  \widetilde{\cdot}\right.  b=ba\qquad\left(  \text{by the
definition of the operation }\left.  \widetilde{\cdot}\right.  \right)  .
\end{align*}
In other words, the ring $R$ is commutative. This proves the \textquotedblleft%
$\Longrightarrow$\textquotedblright\ direction of part \textbf{(b)}.

$\Longleftarrow:$ Assume that $R$ is commutative. We must prove that
$\operatorname{id}:R\rightarrow R$ is a ring isomorphism from $R$ to
$R^{\operatorname{op}}$.

If $a,b\in R$, then%
\begin{align*}
a\left.  \widetilde{\cdot}\right.  b  &  =ba\qquad\left(  \text{by the
definition of the operation }\left.  \widetilde{\cdot}\right.  \right) \\
&  =ab\qquad\left(  \text{since the ring }R\text{ is commutative}\right) \\
&  =a\cdot b.
\end{align*}
Thus, the binary operation $\left.  \widetilde{\cdot}\right.  $ is identical
with the binary operation $\cdot$.

But the only difference between the rings $R$ and $R^{\operatorname*{op}}$ is
that $R^{\operatorname*{op}}$ has the multiplication $\left.  \widetilde{\cdot
}\right.  $ while $R$ has the multiplication $\cdot$. (All the remaining
structure of $R$ and $R^{\operatorname*{op}}$ is the same.) Since we have
shown that $\left.  \widetilde{\cdot}\right.  $ is identical with $\cdot$, we
see that this difference is not actually a difference either; the
multiplications of $R$ and $R^{\operatorname*{op}}$ are also the same. Hence,
the ring $R^{\operatorname*{op}}$ is completely identical to the ring $R$ (not
just as sets, but as rings with all their structure).

But recall that $\operatorname*{id}:R\rightarrow R$ is a ring isomorphism from
$R$ to $R$. Since the ring $R^{\operatorname*{op}}$ is completely identical to
the ring $R$, we can replace the last \textquotedblleft$R$\textquotedblright%
\ in this sentence by \textquotedblleft$R^{\operatorname*{op}}$%
\textquotedblright\ without changing its meaning. Thus, we obtain that
$\operatorname*{id}:R\rightarrow R$ is a ring isomorphism from $R$ to
$R^{\operatorname*{op}}$. This proves the \textquotedblleft$\Longleftarrow
$\textquotedblright\ direction of part \textbf{(b)}.

\bigskip

\textbf{(c)} We shall use some basic properties of transposes of matrices
(see, e.g., \cite[Exercise 6.5]{detnotes}):

\begin{proposition}
\label{prop.sol.ring.op.c.transp.helper}Let $S$ be a commutative ring. In this
proposition, all matrices are over $S$.

\textbf{(a)} If $u$, $v$ and $w$ are three nonnegative integers, if $P$ is a
$u\times v$-matrix, and if $Q$ is a $v\times w$-matrix, then%
\[
\left(  PQ\right)  ^{T}=Q^{T}P^{T}.
\]


\textbf{(b)} Every $u\in\mathbb{N}$ satisfies%
\[
\left(  I_{u}\right)  ^{T}=I_{u}.
\]


\textbf{(c)} If $u$ and $v$ are two nonnegative integers, if $P$ is a $u\times
v$-matrix, and if $\lambda\in S$, then%
\[
\left(  \lambda P\right)  ^{T}=\lambda P^{T}.
\]


\textbf{(d)} If $u$ and $v$ are two nonnegative integers, and if $P$ and $Q$
are two $u\times v$-matrices, then%
\[
\left(  P+Q\right)  ^{T}=P^{T}+Q^{T}.
\]


\textbf{(e)} If $u$ and $v$ are two nonnegative integers, and if $P$ is a
$u\times v$-matrix, then%
\[
\left(  P^{T}\right)  ^{T}=P.
\]

\end{proposition}

Now, let $\mathbf{T}$ be the map%
\[
R\rightarrow R^{\operatorname{op}},\qquad A\mapsto A^{T}.
\]
We must prove that $\mathbf{T}$ is a ring isomorphism.

In Lecture 3, we have proven that any invertible ring morphism is a ring
isomorphism. Hence, it suffices to prove that $\mathbf{T}$ is an invertible
ring morphism.

Let us first prove that $\mathbf{T}$ is a ring morphism. In order to do so, we
need to verify the following four claims:

\begin{statement}
\textit{Claim 1:} We have $\mathbf{T}\left(  a+b\right)  =\mathbf{T}\left(
a\right)  +\mathbf{T}\left(  b\right)  $ for all $a,b\in R$.
\end{statement}

\begin{statement}
\textit{Claim 2:} We have $\mathbf{T}\left(  0_{R}\right)
=0_{R^{\operatorname*{op}}}$.
\end{statement}

\begin{statement}
\textit{Claim 3:} We have $\mathbf{T}\left(  ab\right)  =\mathbf{T}\left(
a\right)  \left.  \widetilde{\cdot}\right.  \mathbf{T}\left(  b\right)  $ for
all $a,b\in R$.
\end{statement}

\begin{statement}
\textit{Claim 4:} We have $\mathbf{T}\left(  1_{R}\right)
=1_{R^{\operatorname*{op}}}$.
\end{statement}

(Note the \textquotedblleft$\left.  \widetilde{\cdot}\right.  $%
\textquotedblright\ sign on the right hand side of Claim 3; this is because
$\mathbf{T}\left(  a\right)  $ and $\mathbf{T}\left(  b\right)  $ are being
considered as elements of $R^{\operatorname*{op}}$, and the multiplication of
the ring $R^{\operatorname*{op}}$ is $\left.  \widetilde{\cdot}\right.  $.)

Let us now prove these claims:

[\textit{Proof of Claim 3:} Let $a,b\in R$. Then, $a\in R=S^{n\times n}$ and
$b\in R=S^{n\times n}$. Hence, $a$ and $b$ are two $n\times n$-matrices over
$S$. The definition of $\mathbf{T}$ yields $\mathbf{T}\left(  ab\right)
=\left(  ab\right)  ^{T}$ and $\mathbf{T}\left(  a\right)  =a^{T}$ and
$\mathbf{T}\left(  b\right)  =b^{T}$. The definition of the operation $\left.
\widetilde{\cdot}\right.  $ yields $\mathbf{T}\left(  a\right)  \left.
\widetilde{\cdot}\right.  \mathbf{T}\left(  b\right)  =\underbrace{\mathbf{T}%
\left(  b\right)  }_{=b^{T}}\underbrace{\mathbf{T}\left(  a\right)  }_{=a^{T}%
}=b^{T}a^{T}$. But $\mathbf{T}\left(  ab\right)  =\left(  ab\right)
^{T}=b^{T}a^{T}$ (by Proposition \ref{prop.sol.ring.op.c.transp.helper}
\textbf{(a)}, applied to $u=n$, $v=n$, $w=n$, $P=a$ and $Q=b$). Comparing
these two equalities, we obtain $\mathbf{T}\left(  ab\right)  =\mathbf{T}%
\left(  a\right)  \left.  \widetilde{\cdot}\right.  \mathbf{T}\left(
b\right)  $. This proves Claim 3.]

[\textit{Proof of Claim 1:} Let $a,b\in R$. Then, $a\in R=S^{n\times n}$ and
$b\in R=S^{n\times n}$. Hence, $a$ and $b$ are two $n\times n$-matrices over
$S$. The definition of $\mathbf{T}$ yields $\mathbf{T}\left(  a+b\right)
=\left(  a+b\right)  ^{T}$ and $\mathbf{T}\left(  a\right)  =a^{T}$ and
$\mathbf{T}\left(  b\right)  =b^{T}$. But $\underbrace{\mathbf{T}\left(
a\right)  }_{=a^{T}}+\underbrace{\mathbf{T}\left(  b\right)  }_{=b^{T}}%
=a^{T}+b^{T}$. But $\mathbf{T}\left(  a+b\right)  =\left(  a+b\right)
^{T}=a^{T}+b^{T}$ (by Proposition \ref{prop.sol.ring.op.c.transp.helper}
\textbf{(d)}, applied to $u=n$, $v=n$, $P=a$ and $Q=b$). Comparing these two
equalities, we obtain $\mathbf{T}\left(  a+b\right)  =\mathbf{T}\left(
a\right)  +\mathbf{T}\left(  b\right)  $. This proves Claim 1.]

[\textit{Proof of Claim 2:} We have $0_{R}=0_{n\times n}$ (by the definition
of the ring $R=S^{n\times n}$). Applying the map $\mathbf{T}$ to both sides of
this equality, we obtain $\mathbf{T}\left(  0_{R}\right)  =\mathbf{T}\left(
0_{n\times n}\right)  =\left(  0_{n\times n}\right)  ^{T}$ (by the definition
of $\mathbf{T}$). But the definition of the transpose of a matrix easily
yields $\left(  0_{n\times n}\right)  ^{T}=0_{n\times n}$. Hence,
$\mathbf{T}\left(  0_{R}\right)  =\left(  0_{n\times n}\right)  ^{T}%
=0_{n\times n}$. But the definition of the ring $R^{\operatorname*{op}}$
yields $0_{R^{\operatorname*{op}}}=0_{R}=0_{n\times n}$. Comparing the latter
two equalities, we obtain $\mathbf{T}\left(  0_{R}\right)
=0_{R^{\operatorname*{op}}}$. This proves Claim 2.]

[\textit{Proof of Claim 4:} We have $1_{R}=I_{n}$ (by the definition of the
ring $R=S^{n\times n}$). Applying the map $\mathbf{T}$ to both sides of this
equality, we obtain $\mathbf{T}\left(  1_{R}\right)  =\mathbf{T}\left(
I_{n}\right)  =\left(  I_{n}\right)  ^{T}$ (by the definition of $\mathbf{T}%
$). But Proposition \ref{prop.sol.ring.op.c.transp.helper} \textbf{(b)}
(applied to $u=n$) yields $\left(  I_{n}\right)  ^{T}=I_{n}$. Hence,
$\mathbf{T}\left(  1_{R}\right)  =\left(  I_{n}\right)  ^{T}=I_{n}$. But the
definition of the ring $R^{\operatorname*{op}}$ yields
$1_{R^{\operatorname*{op}}}=1_{R}=I_{n}$. Comparing the latter two equalities,
we obtain $\mathbf{T}\left(  1_{R}\right)  =1_{R^{\operatorname*{op}}}$. This
proves Claim 4.]

We have now proven all four Claims 1, 2, 3 and 4. Hence, $\mathbf{T}$ is a
ring morphism from $R$ to $R^{\operatorname*{op}}$ (by the definition of a
ring morphism).

Let us next prove that the map $\mathbf{T}$ is invertible. In proving this, we
do not need to concern ourselves with the ring structures (i.e., the
additions, multiplications, zeroes and unities) of $R$ and
$R^{\operatorname*{op}}$, but can simply consider $R$ and
$R^{\operatorname*{op}}$ as sets (because the invertibility of a map has
nothing to do with any ring structures).

Recall that $R^{\operatorname*{op}}=R$ \textbf{as sets}. Thus, the map
$\mathbf{T}$ is a map from $R$ to $R$ (since $\mathbf{T}$ is a map from $R$ to
$R^{\operatorname*{op}}$). Hence, the map $\mathbf{T}\circ\mathbf{T}%
:R\rightarrow R$ is well-defined. Moreover, each $P\in R$ satisfies%
\begin{align*}
\left(  \mathbf{T}\circ\mathbf{T}\right)  \left(  P\right)   &  =\mathbf{T}%
\left(  \underbrace{\mathbf{T}\left(  P\right)  }_{\substack{=P^{T}\\\text{(by
the definition of }\mathbf{T}\text{)}}}\right)  =\mathbf{T}\left(
P^{T}\right)  =\left(  P^{T}\right)  ^{T}\qquad\left(  \text{by the definition
of }\mathbf{T}\right) \\
&  =P\qquad\left(  \text{by Proposition \ref{prop.sol.ring.op.c.transp.helper}
\textbf{(e)} (applied to }u=n\text{ and }v=n\text{)}\right) \\
&  =\operatorname*{id}\left(  P\right)  .
\end{align*}
In other words, $\mathbf{T}\circ\mathbf{T}=\operatorname*{id}$. Hence, the
maps $\mathbf{T}:R\rightarrow R$ and $\mathbf{T}:R\rightarrow R$ are mutually
inverse. Thus, the map $\mathbf{T}:R\rightarrow R$ is invertible. In other
words, the map $\mathbf{T}:R\rightarrow R^{\operatorname*{op}}$ is invertible
(since $R=R^{\operatorname*{op}}$ as sets).

So we have proven that the map $\mathbf{T}:R\rightarrow R^{\operatorname*{op}%
}$ is an invertible ring morphism from $R$ to $R^{\operatorname*{op}}$. Thus,
this map $\mathbf{T}$ is a ring isomorphism from $R$ to $R^{\operatorname*{op}%
}$ (since any invertible ring morphism is a ring isomorphism). This solves
part \textbf{(c)} of the exercise.

\bigskip

\textbf{(d)} We have assumed that $M$ is a right $R$-module. Thus, the module
axioms hold. In other words, the following claims hold:

\begin{statement}
\textit{Claim 5:} The triple $\left(  M,+,0\right)  $ is an abelian group.

\textit{Claim 6:} We have $m\left(  r+s\right)  =mr+ms$ for all $r,s\in R$ and
$m\in M$.

\textit{Claim 7:} We have $\left(  m+n\right)  r=mr+nr$ for all $r\in R$ and
$m,n\in M$.

\textit{Claim 8:} We have $m\left(  rs\right)  =\left(  mr\right)  s$ for all
$r,s\in R$ and $m\in M$.

\textit{Claim 9:} We have $m0_{R}=0_{M}$ for every $m\in M$.

\textit{Claim 10:} We have $0_{M}r=0_{M}$ for every $r\in R$.

\textit{Claim 11:} We have $m1=m$ for every $m\in M$.
\end{statement}

We must prove that $M$ is a left $R^{\operatorname*{op}}$-module. In other
words, we must prove that the module axioms for the left
$R^{\operatorname*{op}}$-module hold:

\begin{statement}
\textit{Claim 12:} The triple $\left(  M,+,0\right)  $ is an abelian group.

\textit{Claim 13:} We have $\left(  r+s\right)  m=rm+sm$ for all $r,s\in
R^{\operatorname*{op}}$ and $m\in M$.

\textit{Claim 14:} We have $r\left(  m+n\right)  =rm+rn$ for all $r\in
R^{\operatorname*{op}}$ and $m,n\in M$.

\textit{Claim 15:} We have $\left(  r\left.  \widetilde{\cdot}\right.
s\right)  m=r\left(  sm\right)  $ for all $r,s\in R^{\operatorname*{op}}$ and
$m\in M$.

\textit{Claim 16:} We have $0_{R}m=0_{M}$ for every $m\in M$.

\textit{Claim 17:} We have $r\cdot0_{M}=0_{M}$ for every $r\in
R^{\operatorname*{op}}$.

\textit{Claim 18:} We have $1m=m$ for every $m\in M$.
\end{statement}

Unsurprisingly, Claims 12--18 follow easily from Claims 5--11. For example,
let us show how Claim 15 follows from Claim 8:

[\textit{Proof of Claim 15:} Let $r,s\in R^{\operatorname*{op}}$ and $m\in M$.
Of course, from $r,s\in R^{\operatorname*{op}}$, we obtain $r,s\in R$ (since
$R^{\operatorname*{op}}=R$ as sets).

The definition of the action of $R^{\operatorname{op}}$ on $M$ yields $sm=ms$
and $r\left(  sm\right)  =\underbrace{\left(  sm\right)  }_{=ms}r=\left(
ms\right)  r$.

Also, the definition of the operation $\left.  \widetilde{\cdot}\right.  $
yields $r\left.  \widetilde{\cdot}\right.  s=sr$. Hence,
\begin{align*}
\left(  r\left.  \widetilde{\cdot}\right.  s\right)  m  &  =\left(  sr\right)
m=m\left(  sr\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of
the action of }R^{\operatorname{op}}\text{ on }M\right) \\
&  =\left(  ms\right)  r\ \ \ \ \ \ \ \ \ \ \left(  \text{by Claim 8, applied
to }s\text{ and }r\text{ instead of }r\text{ and }s\right)  .
\end{align*}
Comparing this with $r\left(  sm\right)  =\left(  ms\right)  r$, we obtain
$\left(  r\left.  \widetilde{\cdot}\right.  s\right)  m=r\left(  sm\right)  $.
This proves Claim 15.]

Thus, we have derived Claim 15 from Claim 8. Similarly, we can derive Claim 13
from Claim 6; Claim 14 from Claim 5; Claim 16 from Claim 9; Claim 17 from
Claim 10; Claim 18 from Claim 11. Of course, Claim 12 is just a copy of Claim 5.

Now, all the Claims 12--18 are proved; thus, $M$ is a left
$R^{\operatorname*{op}}$-module.

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

\section{Exercise 3}

\subsection{Problem}

Let $R$ be an integral domain. Let $a \in R$ and $b \in R$. Assume that $a$
and $b$ have an lcm $\ell\in R$. Prove that $a$ and $b$ have a gcd $g \in R$,
which furthermore satisfies $g\ell= ab$.

[\textbf{Hint:} If $u$ and $v$ are two elements of an integral domain $R$,
with $v \neq0$, then you can use the notation $\dfrac{u}{v}$ (or $u/v$) for
the element $w \in R$ satisfying $u = vw$. This element $w$ does not always
exist, but when it does, it is unique, so the notation is unambiguous. It is
also easy to see that standard rules for fractions, such as $\dfrac{u}{v} +
\dfrac{x}{y} = \dfrac{uy + vx}{vy}$ and $\dfrac{u}{v} \cdot\dfrac{x}{y} =
\dfrac{ux}{vy}$, hold as long as the fractions $\dfrac{u}{v}$ and $\dfrac
{x}{y}$ exist.]

\subsection{Remark}

The converse is not true: The existence of a gcd does not imply the existence
of an lcm.

\subsection{Solution sketch}

We must prove that $a$ and $b$ have a gcd $g\in R$, which furthermore
satisfies $g\ell=ab$. If $a=0$ or $b=0$, then this is easy\footnote{Indeed:
\par
\begin{itemize}
\item If $a=0$, then $b$ is a gcd of $a$ and $b$ (indeed, we have $b\mid0=a$
and $b\mid b$, so that $b$ is a common divisor of $a$ and $b$, and furthermore
it is clear that \textbf{every} common divisor of $a$ and $b$ is a divisor of
$b$), and furthermore satisfies $b\ell=ab$ (indeed, $\ell$ is a multiple of
$a$, so that $\ell=0$ (since $a=0$) and thus $\ell=0=a$, so that $b\ell
=ba=ab$).
\par
\item If $b=0$, then $a$ is a gcd of $a$ and $b$ (for similar reasons), and
furthermore satisfies $a\ell=ab$ (again for similar reasons).
\end{itemize}
}. Hence, for the rest of this proof, we WLOG assume that neither $a=0$ nor
$b=0$ holds. Thus, $a\neq0$ and $b\neq0$. Hence, $ab\neq0$ (since $R$ is an
integral domain).

The element $\ell\in R$ is an lcm of $a$ and $b$. In other words, $\ell$ is a
common multiple of $a$ and $b$ with the property that \textbf{every} common
multiple of $a$ and $b$ is a multiple of $\ell$ (by the definition of an lcm).

In particular, $\ell$ is a common multiple of $a$ and $b$. In other words,
$a\mid\ell$ and $b\mid\ell$. On the other hand, $ab$ is clearly a common
multiple of $a$ and $b$, and thus is a multiple of $\ell$ (since
\textbf{every} common multiple of $a$ and $b$ is a multiple of $\ell$). In
other words, $\ell\mid ab$. Hence, there exists some $m\in R$ such that
$ab=\ell m$. Consider this $m$.

Now, we claim that $m\mid a$. Indeed, there exists some $y\in R$ such that
$\ell=by$ (since $b\mid\ell$). Consider this $y$. Then, $ab=\underbrace{\ell
}_{=by}m=bym$, so that $b\left(  a-ym\right)  =\underbrace{ba}_{=ab=bym}%
-bym=bym-bym=0$. Since $R$ is an integral domain, we thus conclude that $b=0$
or $a-ym=0$. Hence, $a-ym=0$ (since $b\neq0$). Therefore, $a=ym$, so that
$m\mid a$.

A similar argument shows that $m\mid b$. From $m\mid a$ and $m\mid b$, we
conclude that $m$ is a common divisor of $a$ and $b$.

Next, we shall show that \textbf{every} common divisor of $a$ and $b$ is a
divisor of $m$. Indeed, let $d$ be a common divisor of $a$ and $b$. Then,
$d\mid a$ and $d\mid b$.

From $d\mid a\mid ab$, we see that there exists some $z\in R$ such that
$ab=dz$. Consider this $z$.

We shall show that $b\mid z$. Indeed, there exists some $x\in R$ such that
$a=dx$ (since $d\mid a$). Consider this $x$. From $ab=dz$, we obtain
$dz=\underbrace{a}_{=dx}b=dxb$ and thus $\underbrace{a}_{=dx}%
z=dxz=x\underbrace{dz}_{=dxb}=xdxb=\underbrace{dx}_{=a}xb=axb$. Hence,
$a\left(  z-xb\right)  =\underbrace{az}_{=axb}-axb=axb-axb=0$. Since $R$ is an
integral domain, we thus conclude that $a=0$ or $z-xb=0$. Hence, $z-xb=0$
(since $a\neq0$). Therefore, $z=xb$, so that $b\mid z$.

A similar argument shows that $a\mid z$. From $a\mid z$ and $b\mid z$, we
conclude that $z$ is a common multiple of $a$ and $b$. Hence, $z$ is a
multiple of $\ell$ (since \textbf{every} common multiple of $a$ and $b$ is a
multiple of $\ell$). In other words, there exists some $w\in R$ such that
$z=\ell w$. Consider this $w$.

Comparing $ab=\ell m$ with $ab=dz$, we find $\ell m=d\underbrace{z}_{=\ell
w}=d\ell w$. Hence, $\underbrace{ab}_{=\ell m}m=\underbrace{\ell m}_{=d\ell
w}m=d\ell wm=\underbrace{\ell m}_{=ab}dw=abdw$, so that
\[
ab\left(  m-dw\right)  =\underbrace{abm}_{=abdw}-abdw=abdw-abdw=0.
\]
Since $R$ is an integral domain, we thus conclude that $ab=0$ or $m-dw=0$.
Hence, $m-dw=0$ (since $ab\neq0$). Therefore, $m=dw$, so that $d\mid m$. In
other words, $d$ is a divisor of $m$.

Now, forget that we fixed $d$. We thus have shown that every common divisor
$d$ of $a$ and $b$ is a divisor of $m$. Thus, we now know that $m$ is a common
divisor of $a$ and $b$ with the property that \textbf{every} common divisor of
$a$ and $b$ is a divisor of $m$. In other words, $m$ is a gcd of $a$ and $b$
(by the definition of a gcd). Moreover, this gcd $m$ satisfies $m\ell=ab$
(since $m\ell=\ell m=ab$). Hence, $a$ and $b$ have a gcd $g\in R$, which
furthermore satisfies $g\ell=ab$ (namely, $g=m$). This solves the exercise.

\subsection{Remark}

The above solution would have become more transparent if we had used the
fraction notation suggested in the hint. Indeed, using this notation, our
definitions of $m$, $y$, $z$, $x$, $w$ could be rewritten as%
\[
m=\dfrac{ab}{\ell},\ \ \ \ \ \ \ \ \ \ y=\dfrac{\ell}{b}%
,\ \ \ \ \ \ \ \ \ \ z=\dfrac{ab}{d},\ \ \ \ \ \ \ \ \ \ x=\dfrac{a}%
{d},\ \ \ \ \ \ \ \ \ \ w=\dfrac{z}{\ell}.
\]


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

\section{Exercise 4}

\subsection{Problem}

Let $p$ be a prime number.

\begin{itemize}
\item[\textbf{(a)}] Prove that if $a$ and $b$ are two integers such that
$a^{2} \equiv b^{2} \mod p^{2}$, then $a \equiv b \mod p^{2}$ or $a \equiv-b
\mod p^{2}$ or $a \equiv b \equiv0 \mod p$.

\item[\textbf{(b)}] Compute the number of squares in the ring $\mathbb{Z} /
p^{2}$.
\end{itemize}

\subsection{Remark}

This is one more step on our quest to count the squares in $\mathbb{Z} / n$
for an arbitrary positive integer $n$.

\subsection{Solution sketch}

This is rather similar to Exercise 10 on homework set \#1, except that now the
field $F$ has been replaced by the ring $\mathbb{Z}/p^{2}$ (which is not a
field, but behaves similarly in some ways).

\bigskip

\textbf{(a)} Let $a$ and $b$ be two integers such that $a^{2}\equiv
b^{2}\operatorname{mod}p^{2}$. We must prove that $a\equiv b\mod p^{2}$ or
$a\equiv-b\mod p^{2}$ or $a\equiv b\equiv0\mod p$.

We assume the contrary. Thus, we have neither $a\equiv b\mod p^{2}$ or
$a\equiv-b\mod p^{2}$ or $a\equiv b\equiv0\mod p$. We are trying to find a contradiction.

We have $a^{2}\equiv b^{2}\operatorname{mod}p^{2}$, so that $p^{2}\mid
a^{2}-b^{2}$ and therefore $p\mid p^{2}\mid a^{2}-b^{2}$.

We are in one of the following two cases:

\textit{Case 1:} We have $p=2$.

\textit{Case 2:} We have $p\neq2$.

Let us first consider Case 1. In this case, we have $p=2$. Hence, $2=p\mid
a^{2}-b^{2}$. In other words, $a^{2}\equiv b^{2}\operatorname{mod}2$. Now,%
\begin{align*}
\left(  a-b\right)  ^{2}  &  =\underbrace{a^{2}}_{\equiv b^{2}%
\operatorname{mod}2}-\underbrace{2}_{\equiv0\operatorname{mod}2}ab+b^{2}\equiv
b^{2}-0ab+b^{2}=\underbrace{2}_{\equiv0\operatorname{mod}2}b^{2}\\
&  \equiv0b^{2}=0\operatorname{mod}2.
\end{align*}
In other words, $\left(  a-b\right)  ^{2}$ is even. However, if the integer
$a-b$ was odd, then its square $\left(  a-b\right)  ^{2}$ would also be odd
(since the square of an odd integer must be odd); this would contradict the
fact that $\left(  a-b\right)  ^{2}$ is even. Hence, the integer $a-b$ cannot
be odd. Thus, $a-b$ must be even. In other words,
\[
a-b=2u\ \ \ \ \ \ \ \ \ \ \text{for some }u\in\mathbb{Z}.
\]
Consider this $u$.

We have $p=2$ and thus $p^{2}=2^{2}=4$.

We are in one of the following three subcases:

\textit{Subcase 1.1:} The integer $u$ is even.

\textit{Subcase 1.2:} The integer $u+b$ is even.

\textit{Subcase 1.3:} None of the two integers $u$ and $u+b$ is even.

Let us first consider Subcase 1.1. In this subcase, the integer $u$ is even.
Hence, $u=2v$ for some $v\in\mathbb{Z}$. Consider this $v$. Now,
$a-b=2\underbrace{u}_{=2v}=2\cdot2v=4v\equiv0\operatorname{mod}4$, so that
$a\equiv b\operatorname{mod}4$. In other words, $a\equiv b\operatorname{mod}%
p^{2}$ (since $p^{2}=4$). This contradicts the fact that we don't have
$a\equiv b\operatorname{mod}p^{2}$. Hence, we have found a contradiction in
Subcase 1.1.

Let us next consider Subcase 1.2. In this subcase, the integer $u+b$ is even.
Hence, $u+b=2w$ for some $w\in\mathbb{Z}$. Consider this $w$. Now,
\[
a-\left(  -b\right)  =a+b=\underbrace{\left(  a-b\right)  }_{=2u}%
+2b=2u+2b=2\underbrace{\left(  u+b\right)  }_{=w}=2\cdot2w=4w\equiv
0\operatorname{mod}4,
\]
so that $a\equiv-b\operatorname{mod}4$. In other words, $a\equiv
-b\operatorname{mod}p^{2}$ (since $p^{2}=4$). This contradicts the fact that
we don't have $a\equiv-b\operatorname{mod}p^{2}$. Hence, we have found a
contradiction in Subcase 1.2.

Let us next consider Subcase 1.3. In this subcase, none of the two integers
$u$ and $u+b$ is even. Hence, both of these integers are odd. Thus, their sum
$u+\left(  u+b\right)  $ must be even (since a sum of two odd integers is
always even). In other words, $u+\left(  u+b\right)  =2x$ for some
$x\in\mathbb{Z}$. Consider this $x$. Now, $2u+b=u+\left(  u+b\right)  =2x$, so
that $b=2x-2u=2\left(  x-u\right)  \equiv0\operatorname{mod}2$. Also, from
$a-b=2u\equiv0\operatorname{mod}2$, we obtain $a\equiv b\operatorname{mod}2$.
Thus, $a\equiv b\equiv0\operatorname{mod}2$. In other words, $a\equiv
b\equiv0\operatorname{mod}p$ (since $p=2$). This contradicts the fact that we
don't have $a\equiv b\equiv0\operatorname{mod}p$. Hence, we have found a
contradiction in Subcase 1.3.

We have now found a contradiction in each of the three Subcases 1.1, 1.2 and
1.3. Hence, we always obtain a contradiction in Case 1.

Let us now consider Case 2. In this case, we have $p\neq2$. Hence, $p>2$
(since $p$ is a prime).

Recall that $p\mid a^{2}-b^{2}=\left(  a-b\right)  \left(  a+b\right)  $.
Since $p$ is a prime, this entails that we must have $p\mid a-b$ or $p\mid
a+b$ (since a prime that divides a product of two integers must always divide
one of the two factors). Thus, we are in one of the following three subcases:

\textit{Subcase 2.1:} We have $p\mid a-b$ and $p\mid a+b$.

\textit{Subcase 2.2:} We have $p\mid a-b$ but not $p\mid a+b$.

\textit{Subcase 2.3:} We have $p\mid a+b$ but not $p\mid a-b$.

Let us first consider Subcase 2.1. In this case, we have $p\mid a-b$ and
$p\mid a+b$. Now,%
\[
2a=\underbrace{\left(  a-b\right)  }_{\substack{\equiv0\operatorname{mod}%
p\\\text{(since }p\mid a-b\text{)}}}+\underbrace{\left(  a+b\right)
}_{\substack{\equiv0\operatorname{mod}p\\\text{(since }p\mid a+b\text{)}%
}}\equiv0+0=0\operatorname{mod}p,
\]
so that $p\mid2a$. But $p$ is a prime; hence, if $p$ divides a product of two
integers, then $p$ must divide one of its factors. Thus, from $p\mid2a$, we
obtain that $p\mid2$ or $p\mid a$. Since $p\mid2$ is impossible (because
$p\mid2$ would imply $p\leq2$, contradicting $p>2$), we thus must have $p\mid
a$. In other words, $a\equiv0\operatorname{mod}p$. Also, from $p\mid a-b$, we
obtain $a\equiv b\operatorname{mod}p$, so that $b\equiv a\equiv
0\operatorname{mod}p$. Combining this with $a\equiv0\operatorname{mod}p$, we
find $a\equiv b\equiv0\operatorname{mod}p$. This contradicts the fact that we
don't have $a\equiv b\equiv0\operatorname{mod}p$. Hence, we have found a
contradiction in Subcase 2.1.

Let us next consider Subcase 2.2. In this case, we have $p\mid a-b$ but not
$p\mid a+b$.

However, $p$ is a prime. Thus, each integer $k$ is either divisible by $p$ or
coprime to $p$. Applying this to $k=a+b$, we conclude that $a+b$ is either
divisible by $p$ or coprime to $p$. Since $a+b$ is not divisible by $p$
(because we don't have $p\mid a+b$), we thus conclude that $a+b$ is coprime to
$p$. In other words, $p$ is coprime to $a+b$. Hence, $p^{2}$ is coprime to
$a+b$ (since powers of coprime integers are still coprime).

Recall a classical fact from elementary number theory: If three integers $u$,
$v$ and $w$ satisfy $u\mid vw$, and if $u$ is coprime to $v$, then $u\mid w$.
We can apply this to $u=p^{2}$, $v=a+b$ and $w=a-b$ (since $p^{2}\mid
a^{2}-b^{2}=\left(  a+b\right)  \left(  a-b\right)  $, and since $p^{2}$ is
coprime to $a+b$). Thus we obtain $p^{2}\mid a-b$. In other words, $a\equiv
b\operatorname{mod}p^{2}$. This contradicts the fact that we don't have
$a\equiv b\operatorname{mod}p^{2}$. Hence, we have found a contradiction in
Subcase 2.2.

Let us next consider Subcase 2.3. In this case, we have $p\mid a+b$ but not
$p\mid a-b$.

However, $p$ is a prime. Thus, each integer $k$ is either divisible by $p$ or
coprime to $p$. Applying this to $k=a-b$, we conclude that $a-b$ is either
divisible by $p$ or coprime to $p$. Since $a-b$ is not divisible by $p$
(because we don't have $p\mid a-b$), we thus conclude that $a-b$ is coprime to
$p$. In other words, $p$ is coprime to $a-b$. Hence, $p^{2}$ is coprime to
$a-b$ (since powers of coprime integers are still coprime).

Recall a classical fact from elementary number theory: If three integers $u$,
$v$ and $w$ satisfy $u\mid vw$, and if $u$ is coprime to $v$, then $u\mid w$.
We can apply this to $u=p^{2}$, $v=a-b$ and $w=a+b$ (since $p^{2}\mid
a^{2}-b^{2}=\left(  a-b\right)  \left(  a+b\right)  $, and since $p^{2}$ is
coprime to $a-b$). Thus we obtain $p^{2}\mid a+b=a-\left(  -b\right)  $. In
other words, $a\equiv-b\operatorname{mod}p^{2}$. This contradicts the fact
that we don't have $a\equiv-b\operatorname{mod}p^{2}$. Hence, we have found a
contradiction in Subcase 2.3.

We have now found a contradiction in each of the three Subcases 2.1, 2.2 and
2.3. Hence, we always obtain a contradiction in Case 2.

Now we know that we obtain a contradiction in both Cases 1 and 2. This shows
that our assumption was false. Part \textbf{(a)} of the exercise is thus solved.

\bigskip

\textbf{(b)} Let $F=\mathbb{Z}/p^{2}$. Thus, $F$ is a commutative ring of size
$\left\vert F\right\vert =\left\vert \mathbb{Z}/p^{2}\right\vert =p^{2}$.

Note that $F$ is not a field; we have only called it $F$ to stress the analogy
with the $F$ in Exercise 10 on homework set \#1.

We have the following:

\begin{statement}
\textit{Claim 1:} Let $d\in F$. Then:

\textbf{(i)} If $d$ is not a unit of $F$, then $d^{2}=0$.

\textbf{(ii)} If $d$ is a unit of $F$, then $d^{2}$ is a unit of $F$.
\end{statement}

\begin{proof}
[Proof of Claim 1.]\textbf{(i)} Assume that $d$ is not a unit of $F$. We have
$d\in F=\mathbb{Z}/p^{2}$; thus, there exists some $a\in\mathbb{Z}$ such that
$d=\overline{a}$. Consider this $a$. Recall that $d$ is not a unit of $F$. In
other words, $\overline{a}$ is not a unit of $\mathbb{Z}/p^{2}$ (since
$d=\overline{a}$ and $F=\mathbb{Z}/p^{2}$).

Recall the following fact (proven in Lecture 2): The residue class
$\overline{a}\in\mathbb{Z}/n$ (for some integer $n$) is a unit of
$\mathbb{Z}/n$ if and only if $a$ is coprime to $n$. Applying this to
$n=p^{2}$, we conclude that $\overline{a}$ is a unit of $\mathbb{Z}/p^{2}$ if
and only if $a$ is coprime to $p^{2}$. Hence, $a$ is not coprime to $p^{2}$
(since $\overline{a}$ is not a unit of $\mathbb{Z}/p^{2}$).

However, $p$ is a prime. Thus, each integer $k$ is either divisible by $p$ or
coprime to $p$. Applying this to $k=a$, we conclude that $a$ is either
divisible by $p$ or coprime to $p$. Thus, if $a$ was not divisible by $p$,
then $a$ would be coprime to $p$ and therefore also coprime to $p^{2}$ (since
powers of coprime integers are still coprime); but this would contradict the
fact that $a$ is not coprime to $p^{2}$. Hence, $a$ must be divisible by $p$.
Thus, $a^{2}$ is divisible by $p^{2}$. In other words, $a^{2}\equiv
0\operatorname{mod}p^{2}$. In other words, $\overline{a^{2}}=0$ in
$\mathbb{Z}/p^{2}$. Now, from $d=\overline{a}$, we obtain $d^{2}=\overline
{a}^{2}=\overline{a^{2}}=0$. This proves Claim 1 \textbf{(i)}.

\textbf{(ii)} Assume that $d$ is a unit of $F$. Recall that the units of $F$
form a group under multiplication. Hence, any product of two units of $F$ is a
unit of $F$. Thus, the product $dd$ is a unit of $F$ (since $d$ and $d$ are
units of $F$). In other words, $d^{2}$ is a unit of $F$. This proves Claim 1
\textbf{(ii)}.
\end{proof}

\begin{statement}
\textit{Claim 2:} Let $x,y$ be two units of $F$ such that $x^{2}=y^{2}$. Then,
$x=y$ or $x=-y$.
\end{statement}

\begin{proof}
[Proof of Claim 2.]We have $x\in F=\mathbb{Z}/p^{2}$. Thus, there exists some
$a\in\mathbb{Z}$ such that $x=\overline{a}$. Similarly, there exists some
$b\in\mathbb{Z}$ such that $y=\overline{b}$. Consider these $a$ and $b$. We
have assumed that $x^{2}=y^{2}$. In view of $x=\overline{a}$ and
$y=\overline{b}$, this rewrites as $\overline{a}^{2}=\overline{b}^{2}$. Thus,
$\overline{a^{2}}=\overline{a}^{2}=\overline{b}^{2}=\overline{b^{2}}$. In
other words, $a^{2}\equiv b^{2}\operatorname{mod}p^{2}$. According to part
\textbf{(a)} of this exercise, we can thus conclude that $a\equiv
b\operatorname{mod}p^{2}$ or $a\equiv-b\operatorname{mod}p^{2}$ or $a\equiv
b\equiv0\operatorname{mod}p$. Hence, we are in one of the following three cases:

\textit{Case 1:} We have $a\equiv b\operatorname{mod}p^{2}$.

\textit{Case 2:} We have $a\equiv-b\operatorname{mod}p^{2}$.

\textit{Case 3:} We have $a\equiv b\equiv0\operatorname{mod}p$.

Let us first consider Case 1. In this case, we have $a\equiv
b\operatorname{mod}p^{2}$. In other words, $\overline{a}=\overline{b}$ in
$\mathbb{Z}/p^{2}$. Hence, $x=\overline{a}=\overline{b}=y$. Thus, we have
$x=y$ or $x=-y$ (namely, we have $x=y$). Claim 2 is thus proven in Case 1.

Let us next consider Case 2. In this case, we have $a\equiv
-b\operatorname{mod}p^{2}$. In other words, $\overline{a}=\overline{-b}$ in
$\mathbb{Z}/p^{2}$. Hence, $x=\overline{a}=\overline{-b}%
=-\underbrace{\overline{b}}_{=y}=-y$. Thus, we have $x=y$ or $x=-y$ (namely,
we have $x=-y$). Claim 2 is thus proven in Case 2.

Finally, let us consider Case 3. In this case, we have $a\equiv b\equiv
0\operatorname{mod}p$. Hence, $a\equiv0\operatorname{mod}p$, so that $a$ is
divisible by $p$. Thus, $a^{2}$ is divisible by $p^{2}$. In other words,
$a^{2}\equiv0\operatorname{mod}p^{2}$. In other words, $\overline{a^{2}}=0$ in
$\mathbb{Z}/p^{2}$. But $x=\overline{a}$ and thus $x^{2}=\overline{a}%
^{2}=\overline{a^{2}}=0$. However, $x$ is a unit of $F$; thus, we can divide
both sides of this equality $x^{2}=0$ by $x$. We thus obtain $x=0$. Similarly,
we find $y=0$. Thus, $x=0=y$. Hence, we have $x=y$ or $x=-y$ (namely, we have
$x=y$). Claim 2 is thus proven in Case 3.

We have now proven Claim 2 in each of the three Cases 1, 2 and 3. Hence, Claim
2 is proved.
\end{proof}

\begin{statement}
\textit{Claim 3:} Let $c\in F$. Then:

\textbf{(i)} If $c$ is a nonzero square, then%
\[
\left\vert \left\{  d\in F\ \mid\ c=d^{2}\right\}  \right\vert =2.
\]


\textbf{(ii)} If $c$ is not a square, then%
\[
\left\vert \left\{  d\in F\ \mid\ c=d^{2}\right\}  \right\vert =0.
\]


\textbf{(iii)} If $c=0$, then%
\[
\left\vert \left\{  d\in F\ \mid\ c=d^{2}\right\}  \right\vert =p.
\]

\end{statement}

\begin{proof}
[Proof of Claim 3.]\textbf{(i)} Assume that $c$ is a nonzero square. Thus,
there exists a $g\in F$ such that $c=g^{2}$ (since $c$ is a square). Consider
this $g$. Using the ring axioms, we can easily see that $\left(  -g\right)
^{2}=g^{2}$ (just as this identity is proved for numbers). Hence, $c=\left(
-g\right)  ^{2}$ (since $c=g^{2}$). Also, from $c=g^{2}$, we obtain
$g^{2}=c\neq0$ (since $c$ is nonzero).

If $g$ was not a unit of $F$, then we would have $g^{2}=0$ (by Claim 1
\textbf{(i)}, applied to $d=g$); but this would contradict $g^{2}\neq0$.
Hence, $g$ must be a unit of $F$.

Since $p>1$, we have $p^{2}>p\geq2$ and thus $p^{2}\nmid2$. In other words,
$2\not \equiv 0\operatorname{mod}p^{2}$.

We have $F=\mathbb{Z}/p^{2}$ and thus $1_{F}=\overline{1}$, so that
$1_{F}+1_{F}=\overline{1}+\overline{1}=\overline{1+1}=\overline{2}%
\neq\overline{0}$ (since $2\not \equiv 0\operatorname{mod}p^{2}$). In other
words, $1_{F}\neq-1_{F}$.

Now, if we had $g=-g$, then we could divide both sides of this equality by $g$
(since $g$ is a unit of $F$), and thus obtain $1_{F}=-1_{F}$; but this would
contradict $1_{F}\neq-1_{F}$. Hence, we cannot have $g=-g$. Therefore,
$g\neq-g$, so that $\left\vert \left\{  g,-g\right\}  \right\vert =2$.

But both $g$ and $-g$ belong to the set $\left\{  d\in F\ \mid\ c=d^{2}%
\right\}  $ (since $g,-g\in F$ and $c=g^{2}$ and $c=\left(  -g\right)  ^{2}$).
Hence,
\begin{equation}
\left\{  g,-g\right\}  \subseteq\left\{  d\in F\ \mid\ c=d^{2}\right\}  .
\label{sol.Z/p2.squares1.c1.pf.1}%
\end{equation}


On the other hand, let us prove that $\left\{  d\in F\ \mid\ c=d^{2}\right\}
\subseteq\left\{  g,-g\right\}  $. Indeed, let $a\in\left\{  d\in
F\ \mid\ c=d^{2}\right\}  $. Thus, $a$ is an element of $F$ and satisfies
$c=a^{2}$. Hence, $a^{2}=c\neq0$. If $a$ was not a unit of $F$, then we would
have $a^{2}=0$ (by Claim 1 \textbf{(i)}, applied to $d=a$); but this would
contradict $a^{2}\neq0$. Hence, $a$ must be a unit of $F$. Now, we know that
$a$ and $g$ are units of $F$ and satisfy $a^{2}=c=g^{2}$. Hence, Claim 2
(applied to $x=a$ and $y=g$) yields that $a=g$ or $a=-g$. In other words,
$a\in\left\{  g,-g\right\}  $. Now, forget that we fixed $a$. We thus have
shown that $a\in\left\{  g,-g\right\}  $ for each $a\in\left\{  d\in
F\ \mid\ c=d^{2}\right\}  $. In other words, $\left\{  d\in F\ \mid
\ c=d^{2}\right\}  \subseteq\left\{  g,-g\right\}  $. Combining this with
\eqref{sol.Z/p2.squares1.c1.pf.1}, we obtain%
\[
\left\{  d\in F\ \mid\ c=d^{2}\right\}  =\left\{  g,-g\right\}  .
\]
Hence,%
\[
\left\vert \left\{  d\in F\ \mid\ c=d^{2}\right\}  \right\vert =\left\vert
\left\{  g,-g\right\}  \right\vert =2.
\]
This proves Claim 3 \textbf{(i)}.

\textbf{(ii)} Assume that $c$ is not a square. Then, there exists no
$\alpha\in F$ such that $c=\alpha^{2}$ (by the definition of a square). In
other words, there exists no $d\in F$ such that $c=d^{2}$ (here, we have
renamed the index $\alpha$ as $d$). In other words, $\left\{  d\in
F\ \mid\ c=d^{2}\right\}  =\varnothing$. Hence, $\left\vert \left\{  d\in
F\ \mid\ c=d^{2}\right\}  \right\vert =\left\vert \varnothing\right\vert =0$.
This proves Claim 3 \textbf{(ii)}.

\textbf{(iii)} Assume that $c=0$.

Note that the $p$ integers $0p,1p,\ldots,\left(  p-1\right)  p$ are distinct
and all belong to $\left\{  0,1,\ldots,p^{2}-1\right\}  $; hence, their
residue classes $\overline{0p},\overline{1p},\ldots,\overline{\left(
p-1\right)  p}$ modulo $p^{2}$ are distinct. In other words, $\left\vert
\left\{  \overline{0p},\overline{1p},\ldots,\overline{\left(  p-1\right)
p}\right\}  \right\vert =p$.

Let $P$ be the subset $\left\{  \overline{0p},\overline{1p},\ldots
,\overline{\left(  p-1\right)  p}\right\}  $ of $F$. Thus, $P=\left\{
\overline{0p},\overline{1p},\ldots,\overline{\left(  p-1\right)  p}\right\}
$, so that%
\[
\left\vert P\right\vert =\left\vert \left\{  \overline{0p},\overline
{1p},\ldots,\overline{\left(  p-1\right)  p}\right\}  \right\vert =p.
\]


Now, it is easy to see that each $d\in P$ satisfies $c=d^{2}$%
\ \ \ \ \footnote{\textit{Proof.} Let $d\in P$. We must show that $c=d^{2}$.
\par
We have $d\in P=\left\{  \overline{0p},\overline{1p},\ldots,\overline{\left(
p-1\right)  p}\right\}  $. In other words, $d=\overline{kp}$ for some
$k\in\left\{  0,1,\ldots,p-1\right\}  $. Consider this $k$. Now, from
$d=\overline{kp}$, we obtain%
\begin{align*}
d^{2}  &  =\overline{kp}^{2}=\overline{\left(  kp\right)  ^{2}}=\overline
{0}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left(  kp\right)  ^{2}=k^{2}%
p^{2}\equiv0\operatorname{mod}p^{2}\right) \\
&  =0.
\end{align*}
Comparing this with $c=0$, we obtain $c=d^{2}$, qed.}. In other words,
$P\subseteq\left\{  d\in F\ \mid\ c=d^{2}\right\}  $.

On the other hand, let us show that $\left\{  d\in F\ \mid\ c=d^{2}\right\}
\subseteq P$.

Indeed, let $a\in\left\{  d\in F\ \mid\ c=d^{2}\right\}  $. Thus, $a\in F$ and
$c=a^{2}$. Hence, $a^{2}=c=0$.

We have $a\in F=\mathbb{Z}/p^{2}$. In other words, $a=\overline{u}$ for some
$u\in\mathbb{Z}$. Consider this $u$. From $a=\overline{u}$, we obtain
$a^{2}=\overline{u}^{2}=\overline{u^{2}}$, so that $\overline{u^{2}}%
=a^{2}=0=\overline{0}$. In other words, $u^{2}\equiv0\operatorname{mod}p^{2}$.
Hence, $p^{2}\mid u^{2}$. Thus, $\gcd\left(  p^{2},u^{2}\right)  =p^{2}>1$
(since $p>1$).

However, $p$ is a prime. Thus, each integer $k$ is either divisible by $p$ or
coprime to $p$. Applying this to $k=u$, we conclude that $u$ is either
divisible by $p$ or coprime to $p$. Thus, if $u$ was not divisible by $p$,
then $u$ would be coprime to $p$, and therefore $u^{2}$ would be coprime to
$p^{2}$ (since powers of coprime integers are still coprime); but this would
contradict the fact that $\gcd\left(  p^{2},u^{2}\right)  >1$. Hence, $u$ must
be divisible by $p$. In other words, $u=pv$ for some $v\in\mathbb{Z}$.
Consider this $v$.

Let $q$ and $r$ be the quotient and the remainder obtained when dividing $v$
by $p$. Thus, $q\in\mathbb{Z}$ and $r\in\left\{  0,1,\ldots,p-1\right\}  $ and
$v=qp+r$. Now,
\[
u=p\underbrace{v}_{=qp+r}=p\left(  qp+r\right)  =\underbrace{qp^{2}}%
_{\equiv0\operatorname{mod}p^{2}}+rp\equiv rp\operatorname{mod}p^{2},
\]
so that
\begin{align*}
\overline{u}  &  =\overline{rp}\in\left\{  \overline{0p},\overline{1p}%
,\ldots,\overline{\left(  p-1\right)  p}\right\}  \ \ \ \ \ \ \ \ \ \ \left(
\text{since }r\in\left\{  0,1,\ldots,p-1\right\}  \right) \\
&  =P.
\end{align*}
Hence, $a=\overline{u}\in P$.

Now, forget that we fixed $a$. We thus have shown that $a\in P$ for each
$a\in\left\{  d\in F\ \mid\ c=d^{2}\right\}  $. In other words, $\left\{  d\in
F\ \mid\ c=d^{2}\right\}  \subseteq P$. Combining this with $P\subseteq
\left\{  d\in F\ \mid\ c=d^{2}\right\}  $, we obtain $\left\{  d\in
F\ \mid\ c=d^{2}\right\}  =P$. Hence, $\left\vert \left\{  d\in F\ \mid
\ c=d^{2}\right\}  \right\vert =\left\vert P\right\vert =p$. This proves Claim
3 \textbf{(iii)}.
\end{proof}

Now, let us count all pairs $\left(  c,d\right)  \in F\times F$ satisfying
$c=d^{2}$. We shall count these pairs in two ways:

\begin{itemize}
\item The first way is to split this count according to the value of $c$ (that
is, first count all such pairs $\left(  c,d\right)  $ with a given $c$, and
then sum the result up over all $c\in F$). Thus, we find%
\begin{align*}
&  \left(  \text{the number of all }\left(  c,d\right)  \in F\times F\text{
such that }c=d^{2}\right) \\
&  =\sum_{c\in F}\underbrace{\left(  \text{the number of all }d\in F\text{
such that }c=d^{2}\right)  }_{=\left\vert \left\{  d\in F\ \mid\ c=d^{2}%
\right\}  \right\vert }\\
&  =\sum_{c\in F}\left\vert \left\{  d\in F\ \mid\ c=d^{2}\right\}
\right\vert \\
&  =\sum_{\substack{c\in F;\\c=0}}\underbrace{\left\vert \left\{  d\in
F\ \mid\ c=d^{2}\right\}  \right\vert }_{\substack{=p\\\text{(by Claim 3
\textbf{(iii)})}}}+\sum_{\substack{c\in F;\\c\text{ is a nonzero}%
\\\text{square}}}\underbrace{\left\vert \left\{  d\in F\ \mid\ c=d^{2}%
\right\}  \right\vert }_{\substack{=2\\\text{(by Claim 3 \textbf{(i)})}}}\\
&  \qquad+\sum_{\substack{c\in F;\\c\text{ is not a}\\\text{square}%
}}\underbrace{\left\vert \left\{  d\in F\ \mid\ c=d^{2}\right\}  \right\vert
}_{\substack{=0\\\text{(by Claim 3 \textbf{(ii)})}}}\\
&  \qquad\left(
\begin{array}
[c]{c}%
\text{because each }c\in F\text{ satisfies exactly one of the three
statements}\\
\text{\textquotedblleft}c=0\text{\textquotedblright, \textquotedblleft}c\text{
is a nonzero square\textquotedblright\ and \textquotedblleft}c\text{ is not a
square\textquotedblright}%
\end{array}
\right) \\
&  =\underbrace{\sum_{\substack{c\in F;\\c=0}}p}_{\substack{=p\\\text{(since
this sum has}\\\text{exactly one addend)}}}+\underbrace{\sum_{\substack{c\in
F;\\c\text{ is a nonzero}\\\text{square}}}2}_{=2\cdot\left(  \text{the number
of nonzero squares in }F\right)  }+\underbrace{\sum_{\substack{c\in
F;\\c\text{ is not a}\\\text{square}}}0}_{=0}\\
&  =p+2\cdot\left(  \text{the number of nonzero squares in }F\right)  +0\\
&  =p+2\cdot\left(  \text{the number of nonzero squares in }F\right)  .
\end{align*}


\item The second way is to split this count according to the value of $d$
(that is, first count all such pairs $\left(  c,d\right)  $ with a given $d$,
and then sum the result up over all $d\in F$). Thus, we find%
\begin{align*}
&  \left(  \text{the number of all }\left(  c,d\right)  \in F\times F\text{
such that }c=d^{2}\right) \\
&  =\sum_{d\in F}\underbrace{\left(  \text{the number of all }c\in F\text{
such that }c=d^{2}\right)  }_{\substack{=1\\\text{(since there is exactly one
}c\in F\text{ such that }c=d^{2}\text{ (namely, }c=d^{2}\text{))}}}\\
&  =\sum_{d\in F}1=\left\vert F\right\vert \cdot1=\left\vert F\right\vert .
\end{align*}

\end{itemize}

Comparing these two equalities, we obtain%
\[
\left\vert F\right\vert =p+2\cdot\left(  \text{the number of nonzero squares
in }F\right)  .
\]
Solving this for $\left(  \text{the number of nonzero squares in }F\right)  $,
we find%
\[
\left(  \text{the number of nonzero squares in }F\right)  =\dfrac{\left\vert
F\right\vert -p}{2}=\dfrac{p^{2}-p}{2}%
\]
(since $\left\vert F\right\vert =p^{2}$).

Now, there are two kinds of squares in $F$: namely, the nonzero squares (of
which there are exactly $\dfrac{p^{2}-p}{2}$ many, as we just proved) and the
zero squares (of which there is only $1$, namely $0^{2}=0$). Thus, the total
number of squares in $F$ is $\dfrac{p^{2}-p}{2}+1$. In other words, the total
number of squares in $\mathbb{Z}/p^{2}$ is $\dfrac{p^{2}-p}{2}+1$ (since
$F=\mathbb{Z}/p^{2}$). This solves part \textbf{(b)} of the exercise.

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

\section{Exercise 5}

\subsection{Problem}

Let $p$ be a prime number.

\begin{itemize}
\item[\textbf{(a)}] Prove that the only units of the ring $\mathbb{Z} / p$
that are their own inverses (i.e., the only $m \in\left(  \mathbb{Z} / p
\right)  ^{\times}$ that satisfy $m^{-1} = m$) are $\overline{1}$ and
$\overline{-1}$.

\item[\textbf{(b)}] Assume that $p$ is odd. Let $u = \dfrac{p-1}{2}
\in\mathbb{N}$. Prove that $u!^{2} \equiv-\left(  -1 \right)  ^{u} \mod p$.
\end{itemize}

[\textbf{Hint:} The two parts of the exercise are unrelated, other than both
being lemmas in our Lecture 7. For part \textbf{(b)}, recall Wilson's theorem.]

\subsection{Remark}

Part \textbf{(b)} of this exercise easily yields that $u!^{2} \equiv-1 \mod p$
if $p \equiv1 \mod 4$ (since $p \equiv1 \mod 4$ entails that $u$ is even).
This is one of the facts we used in Lecture 7.]

\subsection{Solution}

\textbf{(a)} We have $\overline{1}\cdot\overline{1}=\overline{1\cdot
1}=\overline{1}$ and $\overline{-1}\cdot\overline{-1}=\overline{\left(
-1\right)  \cdot\left(  -1\right)  }=\overline{1}$. Thus, the elements
$\overline{1}$ and $\overline{-1}$ of $\mathbb{Z}/p$ are inverse to
themselves. Hence, these elements $\overline{1}$ and $\overline{-1}$ have
inverses, i.e., are units of $\mathbb{Z}/p$. Since they are inverse to
themselves, we thus conclude that they are units of the ring $\mathbb{Z}/p$
that are their own inverses.

It remains to prove that they are the \textbf{only} such units. In other
words, it remains to prove that if $a$ is a unit of $\mathbb{Z}/p$ that is its
own inverse, then $a$ equals $\overline{1}$ or $\overline{-1}$.

So let $a$ be a unit of $\mathbb{Z}/p$ that is its own inverse. We must prove
that $a$ equals $\overline{1}$ or $\overline{-1}$.

Indeed, $\mathbb{Z}/p$ is a field (since $p$ is prime), hence an integral
domain. But $a$ is its own inverse; in other words, $aa=\overline{1}$ (since
$\overline{1}$ is the unity of the ring $\mathbb{Z}/p$). Now, $\left(
a-\overline{1}\right)  \left(  a+\overline{1}\right)  =a^{2}-\overline{1}%
^{2}=0$ (since $a^{2}=aa=\overline{1}=\overline{1}^{2}$). Since $\mathbb{Z}/p$
is an integral domain, we thus conclude that we have $a-\overline{1}=0$ or
$a+\overline{1}=0$. In other words, we have $a=\overline{1}$ or $a=-\overline
{1}$. In other words, $a$ equals $\overline{1}$ or $-\overline{1}$. In other
words, $a$ equals $\overline{1}$ or $\overline{-1}$ (since $-\overline
{1}=\overline{-1}$). But this is precisely what we wanted to prove. Thus, the
solution to part \textbf{(a)} is complete.

\bigskip

\textbf{(b)} We have $p-1=2u$ (since $u=\dfrac{p-1}{2}$), so that $p-2u=1$.
Also, $p-\left(  u+1\right)  =\underbrace{p-1}_{=2u}-u=2u-u=u$.

Wilson's theorem yields $\left(  p-1\right)  !\equiv-1\operatorname{mod}p$.
Hence,%
\begin{align}
-1  &  \equiv\left(  p-1\right)  !\nonumber\\
&  =1\cdot2\cdot\cdots\cdot\left(  p-1\right) \nonumber\\
&  =1\cdot2\cdot\cdots\cdot\left(  2u\right)  \ \ \ \ \ \ \ \ \ \ \left(
\text{since }p-1=2u\right) \nonumber\\
&  =\left(  1\cdot2\cdot\cdots\cdot u\right)  \cdot\left(  \left(  u+1\right)
\cdot\left(  u+2\right)  \cdot\cdots\cdot\left(  2u\right)  \right)
\operatorname{mod}p. \label{sol.ent.wilson-lem.b.1}%
\end{align}
However,
\begin{align*}
&  \left(  u+1\right)  \cdot\left(  u+2\right)  \cdot\cdots\cdot\left(
2u\right) \\
&  =\prod_{k=u+1}^{2u}k=\prod_{j=p-2u}^{p-\left(  u+1\right)  }%
\underbrace{\left(  p-j\right)  }_{\equiv-j\operatorname{mod}p}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }p-j\text{ for
}k\text{ in the product}\right) \\
&  \equiv\prod_{j=p-2u}^{p-\left(  u+1\right)  }\left(  -j\right)
=\prod_{j=1}^{u}\left(  -j\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since
}p-2u=1\text{ and }p-\left(  u+1\right)  =u\right) \\
&  =\left(  -1\right)  ^{u}\underbrace{\prod_{j=1}^{u}j}_{=1\cdot2\cdot
\cdots\cdot u=u!}=\left(  -1\right)  ^{u}u!\operatorname{mod}p.
\end{align*}
Hence, \eqref{sol.ent.wilson-lem.b.1} becomes%
\[
-1\equiv\underbrace{\left(  1\cdot2\cdot\cdots\cdot u\right)  }_{=u!}%
\cdot\underbrace{\left(  \left(  u+1\right)  \cdot\left(  u+2\right)
\cdot\cdots\cdot\left(  2u\right)  \right)  }_{\equiv\left(  -1\right)
^{u}u!\operatorname{mod}p}\equiv u!\cdot\left(  -1\right)  ^{u}u!=\left(
-1\right)  ^{u}\left(  u!\right)  ^{2}\operatorname{mod}p.
\]
Multiplying both sides of this congruence by $\left(  -1\right)  ^{u}$, we
obtain%
\[
-\left(  -1\right)  ^{u}\equiv\underbrace{\left(  -1\right)  ^{u}\left(
-1\right)  ^{u}}_{=\left(  -1\right)  ^{2u}=1}\left(  u!\right)  ^{2}=\left(
u!\right)  ^{2}\operatorname{mod}p.
\]
Thus, $\left(  u!\right)  ^{2}\equiv-\left(  -1\right)  ^{u}\operatorname{mod}%
p$. This solves part \textbf{(b)} of the exercise.

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

\section{Exercise 6}

\subsection{Problem}

Recall the ring $\mathbb{Z}\left[  i \right]  $ of Gaussian integers. Let $N :
\mathbb{Z}\left[  i \right]  \to\mathbb{N}$ be the map that sends each
Gaussian integer $z = a + bi \in\mathbb{Z}\left[  i \right]  $ (with $a, b
\in\mathbb{Z}$) to $a^{2} + b^{2} = \left|  z \right|  ^{2}$. (This is the
Euclidean norm on $\mathbb{Z}\left[  i \right]  $ that we have already used
several times.)

\begin{itemize}
\item[\textbf{(a)}] Prove that if $z$ and $w$ are two Gaussian integers
satisfying $z \mid w$ in $\mathbb{Z}\left[  i \right]  $, then $N\left(  z
\right)  \mid N\left(  w \right)  $ in $\mathbb{Z}$.

\item[\textbf{(b)}] Let $z=a+bi\in\mathbb{Z}\left[  i\right]  $ with
$a,b\in\mathbb{Z}$. Assume that $z\neq0$. Let $n=\left\lfloor \left\vert
z\right\vert \right\rfloor =\left\lfloor \sqrt{a^{2}+b^{2}}\right\rfloor $.
Prove that every divisor of $z$ in $\mathbb{Z}\left[  i\right]  $ has the form
$c+di$ with $c,d\in\left\{  -n,-n+1,\ldots,n\right\}  $.

\item[\textbf{(c)}] Without recourse to the general theory of PIDs and UFDs,
prove that every nonzero element of $\mathbb{Z}\left[  i \right]  $ has an
irreducible factorization.

\item[\textbf{(d)}] Let $z \in\mathbb{Z}\left[  i \right]  $. Prove that we
have the following logical equivalence:
\[
\left(  z \text{ is a unit of } \mathbb{Z}\left[  i \right]  \right)
\ \iff\ \left(  N\left(  z \right)  = 1 \right)  \ \iff\ \left(  z \in\left\{
1, i, -1, -i \right\}  \right)  .
\]

\end{itemize}

\subsection{Remark}

Combining parts \textbf{(b)} and \textbf{(c)} of this exercise yields a (slow)
algorithm for finding an irreducible factorization of a nonzero Gaussian
integer. (Indeed, part \textbf{(b)} shows that we can list all divisors of a
nonzero Gaussian integer in finite time. This allows checking whether a
Gaussian integer is prime, and otherwise finding a prime divisor.)

\subsection{Solution sketch}

Recall that
\begin{equation}
N\left(  \alpha\beta\right)  =N\left(  \alpha\right)  N\left(  \beta\right)
\ \ \ \ \ \ \ \ \ \ \text{for any }\alpha,\beta\in\mathbb{Z}\left[  i\right]
. \label{sol.Zi.basics-div.1}%
\end{equation}
(This was a proposition in Lecture 7.)

We also observe that if $\alpha$ is a Gaussian integer satisfying $\alpha
\neq0$, then%
\begin{equation}
N\left(  \alpha\right)  \text{ is a positive integer.}
\label{sol.Zi.basics-div.2}%
\end{equation}


[\textit{Proof of \eqref{sol.Zi.basics-div.2}:} Let $\alpha$ be a Gaussian
integer satisfying $\alpha\neq0$. Then, $\alpha=a+bi$ for some $a,b\in
\mathbb{Z}$ (since $\alpha$ is a Gaussian integer). Consider these $a,b$. We
have $\alpha=a+bi$ (with $a,b\in\mathbb{Z}$) and thus $N\left(  \alpha\right)
=a^{2}+b^{2}$ (by the definition of $N$). However, at least one of the two
integers $a$ and $b$ is nonzero (since otherwise, we would have $a=0$ and
$b=0$ and thus $\alpha=\underbrace{a}_{=0}+\underbrace{b}_{=0}i=0$,
contradicting $\alpha\neq0$). Hence, at least one of the two nonnegative
integers $a$ and $b$ is positive. Thus, $a^{2}+b^{2}$ is a positive integer
(being a sum of a nonnegative and a positive integer). In other words,
$N\left(  \alpha\right)  $ is a positive integer (since $N\left(
\alpha\right)  =a^{2}+b^{2}$). This proves \eqref{sol.Zi.basics-div.2}.]

\bigskip

\textbf{(a)} Let $z$ and $w$ be two Gaussian integers satisfying $z\mid w$ in
$\mathbb{Z}\left[  i\right]  $. From $z\mid w$, we see that there exists a
$u\in\mathbb{Z}\left[  i\right]  $ such that $w=zu$. Consider this $u$. From
$w=zu$, we obtain $N\left(  w\right)  =N\left(  zu\right)  =N\left(  z\right)
N\left(  u\right)  $ (by \eqref{sol.Zi.basics-div.1}). Since $N\left(
u\right)  \in\mathbb{N}\subseteq\mathbb{Z}$, this entails $N\left(  z\right)
\mid N\left(  w\right)  $ in $\mathbb{Z}$. This solves part \textbf{(a)} of
the problem.

\bigskip

\textbf{(b)} Let $w$ be a divisor of $z$ in $\mathbb{Z}\left[  i\right]  $.
Thus, $w\in\mathbb{Z}\left[  i\right]  $, so that we can write $w$ in the form
$w=c+di$ for some $c,d\in\mathbb{Z}$. Consider these $c,d$. We must thus prove
that $c,d\in\left\{  -n,-n+1,\ldots,n\right\}  $.

We have $z=a+bi$ (with $a,b\in\mathbb{Z}$) and thus $N\left(  z\right)
=a^{2}+b^{2}$ (by the definition of $N$). Also, $N\left(  z\right)  $ is a
positive integer (by \eqref{sol.Zi.basics-div.2}, applied to $\alpha=z$).

We have $w=c+di$ (with $c,d\in\mathbb{Z}$) and thus $N\left(  w\right)
=c^{2}+d^{2}$ (by the definition of $N$). However, $w\mid z$ in $\mathbb{Z}%
\left[  i\right]  $ (since $w$ is a divisor of $z$), and thus $N\left(
w\right)  \mid N\left(  z\right)  $ in $\mathbb{Z}$ (by part \textbf{(a)} of
this exercise, applied to $w$ and $z$ instead of $z$ and $w$). Since $N\left(
z\right)  $ is positive and $N\left(  w\right)  $ is nonnegative, this entails
that $N\left(  w\right)  \leq N\left(  z\right)  =a^{2}+b^{2}$.

Hence, $a^{2}+b^{2}\geq N\left(  w\right)  =c^{2}+\underbrace{d^{2}}_{\geq
0}\geq c^{2}$. Since both sides of this inequality are nonnegative, we can
take square roots and obtain $\sqrt{a^{2}+b^{2}}\geq\sqrt{c^{2}}=\left\vert
c\right\vert $. Hence, $\left\vert c\right\vert \leq\sqrt{a^{2}+b^{2}}$.
Therefore, $\left\vert c\right\vert $ is an integer that is $\leq\sqrt
{a^{2}+b^{2}}$ (since $\left\vert c\right\vert $ is clearly an integer). Since
$\left\lfloor \sqrt{a^{2}+b^{2}}\right\rfloor $ is the \textbf{largest}
integer that is $\leq\sqrt{a^{2}+b^{2}}$, we thus conclude that $\left\vert
c\right\vert \leq\left\lfloor \sqrt{a^{2}+b^{2}}\right\rfloor $. In other
words, $\left\vert c\right\vert \leq n$ (since $n=\left\lfloor \sqrt
{a^{2}+b^{2}}\right\rfloor $). Thus, $c\in\left\{  -n,-n+1,\ldots,n\right\}  $
(since $c$ is an integer). A similar argument (using $\underbrace{c^{2}}%
_{\geq0}+d^{2}\geq d^{2}$ instead of $c^{2}+\underbrace{d^{2}}_{\geq0}\geq
c^{2}$) shows that $d\in\left\{  -n,-n+1,\ldots,n\right\}  $. Thus, we have
proved that $c,d\in\left\{  -n,-n+1,\ldots,n\right\}  $. Part \textbf{(b)} of
the exercise is solved.

\bigskip

\textbf{(d)} See \cite[Proposition 4.2.9 \textbf{(b)}]{19s} for a proof of the
equivalence $\left(  z\text{ is a unit of }\mathbb{Z}\left[  i\right]
\right)  \ \iff\ \left(  N\left(  z\right)  =1\right)  $, and see
\cite[Proposition 4.2.10]{19s} for a proof of the equivalence \newline$\left(
z\text{ is a unit of }\mathbb{Z}\left[  i\right]  \right)  \ \iff\ \left(
z\in\left\{  1,i,-1,-i\right\}  \right)  $. (They are both rather easy: The
first uses \eqref{sol.Zi.basics-div.1} and the fact that $N\left(  z\right)
=z\overline{z}$; the second uses the first along with the fact that two
integers $a,b$ satisfy $a^{2}+b^{2}=1$ if and only if one of $\left\vert
a\right\vert $ and $\left\vert b\right\vert $ is $0$ and the other is $1$.)

\bigskip

\textbf{(c)} We imitate the classical proof that every positive integer has a
prime factorization:

We must prove that every nonzero $z\in\mathbb{Z}\left[  i\right]  $ has an
irreducible factorization. We proceed by strong induction on $N\left(
z\right)  $ (using the fact that $N\left(  z\right)  \in\mathbb{N}$ for each
$z\in\mathbb{Z}\left[  i\right]  $).

\textit{Induction step:} Let $m\in\mathbb{N}$. Assume (as induction
hypothesis) that every nonzero $z\in\mathbb{Z}\left[  i\right]  $ satisfying
$N\left(  z\right)  <m$ has an irreducible factorization. We must show that
every nonzero $z\in\mathbb{Z}\left[  i\right]  $ satisfying $N\left(
z\right)  =m$ has an irreducible factorization.

Indeed, let $z\in\mathbb{Z}\left[  i\right]  $ be nonzero and satisfy
$N\left(  z\right)  =m$. We must prove that $z$ has an irreducible
factorization. If $z$ is a unit, then this is obvious (because in this case,
the empty list $\left(  {}\right)  $ is an irreducible factorization of $z$);
it is also obvious if $z$ is irreducible (since in this case, the list
$\left(  z\right)  $ is an irreducible factorization of $z$). Thus, for the
rest of this proof, we WLOG assume that $z$ is neither a unit nor irreducible.
Hence, there exist $a,b\in\mathbb{Z}\left[  i\right]  $ such that $ab=z$ and
such that neither $a$ nor $b$ is a unit (by the definition of
\textquotedblleft irreducible\textquotedblright).\footnote{For constructivists
or algorithmists, it is important to notice that all these distinctions and
existence statements are constructive. Indeed, there is a simple algorithm for
checking whether two Gaussian integers $\alpha$ and $\beta$ satisfy
$\alpha\mid\beta$ (namely, if $\alpha=0$, then $\alpha\mid\beta$ holds if and
only if $\beta=0$; but otherwise, you can just compute the complex number
$\dfrac{\beta}{\alpha}\in\mathbb{Q}\left[  i\right]  $ and check whether its
real and imaginary part are integers). Thus, we can check whether $z$ is a
unit (indeed, $z$ is a unit if and only if $z\mid1$). Furthermore, part
\textbf{(b)} of this exercise tells us that all divisors of $z$ in
$\mathbb{Z}\left[  i\right]  $ have the form $c+di$ for some $c,d\in\left\{
-n,-n+1,\ldots,n\right\}  $, where $n=\left\lfloor \left\vert z\right\vert
\right\rfloor =\left\lfloor \sqrt{a^{2}+b^{2}}\right\rfloor $; thus, we can
compute a list of all divisors of $z$ in $\mathbb{Z}\left[  i\right]  $
(simply by running through all the $\left(  2n+1\right)  ^{2}$ numbers of this
form, and checking each of them for being a divisor of $z$). Thus, we can find
all possible pairs $\left(  a,b\right)  $ of Gaussian integers $a,b\in
\mathbb{Z}\left[  i\right]  $ satisfying $ab=z$ (because both entries in such
a pair $\left(  a,b\right)  $ must be divisors of $z$ in $\mathbb{Z}\left[
i\right]  $). This allows us to check whether $z$ is irreducible, and, in case
the answer is \textquotedblleft no\textquotedblright, to actually construct a
pair $\left(  a,b\right)  $ with $ab=z$ and such that neither $a$ nor $b$ is a
unit.} Consider these $a,b$.

From $ab=z$, we obtain $z=ab$ and thus $N\left(  z\right)  =N\left(
ab\right)  =N\left(  a\right)  N\left(  b\right)  $ (by
\eqref{sol.Zi.basics-div.1}). Note that $z\neq0$ (since $z$ is nonzero);
hence, $N\left(  z\right)  $ is a positive integer (by
\eqref{sol.Zi.basics-div.2}). From $ab=z\neq0$, we obtain $a\neq0$. Hence,
$N\left(  a\right)  $ is a positive integer (by \eqref{sol.Zi.basics-div.2}),
and the Gaussian integer $a$ is nonzero.

Part \textbf{(d)} of this exercise (applied to $a$ instead of $z$) shows that
we have the equivalence%
\[
\left(  a\text{ is a unit of }\mathbb{Z}\left[  i\right]  \right)
\ \iff\ \left(  N\left(  a\right)  =1\right)  \ \iff\ \left(  a\in\left\{
1,i,-1,-i\right\}  \right)  .
\]
Hence, we don't have $N\left(  a\right)  =1$ (since $a$ is not a unit of
$\mathbb{Z}\left[  i\right]  $). Thus, $N\left(  a\right)  \neq1$, so that
$N\left(  a\right)  >1$ (since $N\left(  a\right)  $ is a positive integer).
Likewise, $N\left(  b\right)  >1$.

Now, from $N\left(  a\right)  >1$ and $N\left(  b\right)  >1$, we obtain
$N\left(  a\right)  N\left(  b\right)  >N\left(  a\right)  $, so that
$N\left(  a\right)  <N\left(  a\right)  N\left(  b\right)  =N\left(  z\right)
$ (since $N\left(  z\right)  =N\left(  a\right)  N\left(  b\right)  $). Thus,
$N\left(  a\right)  <N\left(  z\right)  =m$. Hence, by our induction
hypothesis, $a$ has an irreducible factorization (since $a$ is a nonzero
element of $\mathbb{Z}\left[  i\right]  $). Similarly, $b$ has an irreducible
factorization. Let these two irreducible factorizations be $\left(
a_{1},a_{2},\ldots,a_{k}\right)  $ and $\left(  b_{1},b_{2},\ldots,b_{\ell
}\right)  $. Thus, $a\sim a_{1}a_{2}\cdots a_{k}$ and $b\sim b_{1}b_{2}\cdots
b_{\ell}$. Hence, it is easy to see that $ab\sim a_{1}a_{2}\cdots a_{k}%
b_{1}b_{2}\cdots b_{\ell}$. Thus, $ab$ has an irreducible factorization
(namely, $\left(  a_{1},a_{2},\ldots,a_{k},b_{1},b_{2},\ldots,b_{\ell}\right)
$). In other words, $z$ has an irreducible factorization (since $z=ab$). This
completes our induction step. Thus, part \textbf{(c)} of the exercise is solved.

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

\section{Exercise 7}

\subsection{Problem}

Consider the ring
\[
\mathbb{Z}\left[  \sqrt{-3} \right]  = \left\{  a + b \sqrt{-3} \mid a, b
\in\mathbb{Z} \right\}  .
\]
This ring is a subring of $\mathbb{C}$, and thus is an integral domain.

Let $u = 2 \in\mathbb{Z}\left[  \sqrt{-3} \right]  $ and $v = 1 + \sqrt{-3}
\in\mathbb{Z}\left[  \sqrt{-3} \right]  $. Further let $a = 2u = 4$ and $b =
2v$.

\begin{itemize}
\item[\textbf{(a)}] Prove that both $u$ and $v$ are common divisors of $a$ and
$b$ in $\mathbb{Z}\left[  \sqrt{-3} \right]  $.

\item[\textbf{(b)}] Prove that the only divisors of $4$ in $\mathbb{Z}\left[
\sqrt{-3} \right]  $ are $\pm1$, $\pm2$, $\pm4$, $\pm\left(  1 + \sqrt{-3}
\right)  $, and $\pm\left(  1 - \sqrt{-3} \right)  $.

\item[\textbf{(c)}] Prove that $a$ and $b$ have no gcd in $\mathbb{Z}\left[
\sqrt{-3} \right]  $.
\end{itemize}

[\textbf{Hint:} For full credits on part \textbf{(b)}, it suffices to explain
how the solution can be reduced to a finite computation and perform one
representative case of the computation.]

\subsection{Remark}

This shows that $\mathbb{Z}\left[  \sqrt{-3} \right]  $ is not a UFD.

\subsection{Solution}

...

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

\section{Exercise 8}

\subsection{Problem}

Let $R$ be a ring. Let $I$ and $J$ be two ideals of $R$ such that $I \subseteq
J$. Let $J / I$ denote the set of all cosets $j + I \in R / I$ where $j \in J$.

Prove the following:

\begin{itemize}
\item[\textbf{(a)}] This set $J / I$ is an ideal of $R / I$.

\item[\textbf{(b)}] We have $\left(  R / I \right)  / \left(  J / I \right)
\cong R / J$ (as rings). More concretely, there is a ring isomorphism $R / J
\to\left(  R / I \right)  / \left(  J / I \right)  $ that sends each residue
class $\overline{r} = r + J$ to $\overline{r + I} = \left(  r + I \right)  +
\left(  J / I \right)  $.
\end{itemize}

\subsection{Remark}

This is known as the \emph{Third Isomorphism Theorem for rings}.

For an example, take $R = \mathbb{Z}$ and $I = 6 \mathbb{Z}$ and $J = 2
\mathbb{Z}$. In this case, $J / I$ consists of the ``even'' residue classes
$\overline{0}, \overline{2}, \overline{4}$ in $R / I = \mathbb{Z} / 6$. Part
\textbf{(b)} of the exercise says that if we ``quotient them out'' of
$\mathbb{Z} / 6$, then we are left with (an isomorphic copy of) $R / J =
\mathbb{Z} / 2$.

\subsection{Solution}

This can be solved in a pretty straightforward manner (i.e., checking the
ideal axioms for part \textbf{(a)}, then constructing the isomorphism in part
\textbf{(b)} and proving the requisite properties). However, here is a more
elegant approach:

Consider the canonical projection%
\begin{align*}
\pi_{I}:R  &  \rightarrow R/I,\\
r  &  \mapsto r+I.
\end{align*}
This projection $\pi_{I}$ is a surjective ring morphism from $R$ to $R/I$.

Consider the canonical projection%
\begin{align*}
\pi_{J}:R  &  \rightarrow R/J,\\
r  &  \mapsto r+J.
\end{align*}
This projection $\pi_{J}$ is a surjective ring morphism from $R$ to $R/J$.

The definition of $\pi_{J}$ shows that for each $i\in I$, we have $\pi
_{J}\left(  i\right)  =i+J=0$ (since $i\in I\subseteq J$). In other words, the
map $\pi_{J}$ sends each $i\in I$ to $0$. In other words, $\pi_{J}\left(
I\right)  =0$. Hence, the universal property of quotient rings (applied to
$S=R/J$, $\pi=\pi_{I}$ and $f=\pi_{J}$) shows that there is a unique ring
morphism $\pi_{J}^{\prime}:R/I\rightarrow R/J$ satisfying $\pi_{J}=\pi
_{J}^{\prime}\circ\pi_{I}$. Consider this $\pi_{J}^{\prime}$. Thus, for each
$r\in R$, we have%
\begin{align}
r+J  &  =\pi_{J}\left(  r\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }%
\pi_{J}\left(  r\right)  \text{ is defined to be }r+J\right) \nonumber\\
&  =\left(  \pi_{J}^{\prime}\circ\pi_{I}\right)  \left(  r\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\pi_{J}=\pi_{J}^{\prime}\circ\pi
_{I}\right) \nonumber\\
&  =\pi_{J}^{\prime}\left(  \underbrace{\pi_{I}\left(  r\right)
}_{\substack{=r+I\\\text{(by the definition of }\pi_{I}\text{)}}}\right)
\nonumber\\
&  =\pi_{J}^{\prime}\left(  r+I\right)  . \label{pf.thm.3it.1}%
\end{align}


Recall that $\pi_{J}^{\prime}$ is a ring morphism from $R/I$ to $R/J$. Thus,
the definition of $\operatorname*{Ker}\left(  \pi_{J}^{\prime}\right)  $
yields%
\begin{align*}
\operatorname*{Ker}\left(  \pi_{J}^{\prime}\right)   &  =\left\{  a\in
R/I\ \mid\ \pi_{J}^{\prime}\left(  a\right)  =0_{R/J}\right\} \\
&  =\left\{  r+I\ \mid\ r\in R\text{ such that }\underbrace{\pi_{J}^{\prime
}\left(  r+I\right)  }_{\substack{=r+J\\\text{(by (\ref{pf.thm.3it.1}))}%
}}=0_{R/J}\right\} \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have substituted }r+I\text{ for }a\text{, since every}\\
\text{element of }R/I\text{ has the form }r+I\text{ for some }r\in R
\end{array}
\right) \\
&  =\left\{  r+I\ \mid\ r\in R\text{ such that }r+J=0_{R/J}\right\} \\
&  =\left\{  r+I\ \mid\ r\in J\right\}  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the elements }r\in R\text{ that satisfy }r+J=0_{R/J}\\
\text{are precisely the elements of }J
\end{array}
\right) \\
&  =\left\{  j+I\ \mid\ j\in J\right\}  \ \ \ \ \ \ \ \ \ \ \left(
\text{here, we have renamed the index }r\text{ as }j\right) \\
&  =J/I\ \ \ \ \ \ \ \ \ \ \left(  \text{since }J/I\text{ was defined to be
}\left\{  j+I\ \mid\ j\in J\right\}  \right)  .
\end{align*}
However, $\operatorname*{Ker}\left(  \pi_{J}^{\prime}\right)  $ is an ideal of
$R/I$ (since the kernel of a ring morphism is always an ideal of the domain).
In other words, $J/I$ is an ideal of $R/I$ (since $\operatorname*{Ker}\left(
\pi_{J}^{\prime}\right)  =J/I$). This solves part \textbf{(a)} of the
exercise. \medskip

\textbf{(b)} The morphism $\pi_{J}^{\prime}$ is
surjective\footnote{\textit{Proof.} Let $u\in R/J$. Thus, $u=r+J$ for some
$r\in R$. Consider this $r$. Hence, $u=r+J=\pi_{J}^{\prime}\left(  r+I\right)
$ (by (\ref{pf.thm.3it.1})). Thus, $u\in\pi_{J}^{\prime}\left(  R/I\right)  $
(since $r+I\in R/I$).
\par
Forget that we fixed $u$. We thus have shown that $u\in\pi_{J}^{\prime}\left(
R/I\right)  $ for each $u\in R/J$. In other words, $R/J\subseteq\pi
_{J}^{\prime}\left(  R/I\right)  $. In other words, $\pi_{J}^{\prime}$ is
surjective.}. Thus,
\[
\pi_{J}^{\prime}\left(  R/I\right)  =R/J.
\]


Now, $\pi_{J}^{\prime}$ is a ring morphism from $R/I$ to $R/J$. Thus, the
first isomorphism theorem (applied to $R/I$, $R/J$ and $\pi_{J}^{\prime}$
instead of $R$, $S$ and $f$) yields that we have
\begin{equation}
\left(  R/I\right)  /\operatorname*{Ker}\left(  \pi_{J}^{\prime}\right)
\cong\pi_{J}^{\prime}\left(  R/I\right)  , \label{pf.thm.3it.b.1}%
\end{equation}
and more precisely, the universal property of quotient rings yields a ring
morphism%
\[
f^{\prime}:\left(  R/I\right)  /\operatorname*{Ker}\left(  \pi_{J}^{\prime
}\right)  \rightarrow R/J,
\]
which (if we restrict its target to its actual image $\pi_{J}^{\prime}\left(
R/I\right)  $) is a ring isomorphism from $\left(  R/I\right)
/\operatorname*{Ker}\left(  \pi_{J}^{\prime}\right)  $ to $\pi_{J}^{\prime
}\left(  R/I\right)  $. Consider this ring morphism $f^{\prime}$.

In view of $\operatorname*{Ker}\left(  \pi_{J}^{\prime}\right)  =J/I$ and
$\pi_{J}^{\prime}\left(  R/I\right)  =R/J$, we can rewrite
(\ref{pf.thm.3it.b.1}) as $\left(  R/I\right)  /\left(  J/I\right)  \cong
R/J$. Thus, we have shown that $\left(  R/I\right)  /\left(  J/I\right)  \cong
R/J$ (as rings). It remains to prove the \textquotedblleft More
concretely\textquotedblright\ part of part \textbf{(b)} -- i.e., to show that
there is a ring isomorphism $R/J\rightarrow\left(  R/I\right)  /\left(
J/I\right)  $ that sends each residue class $\overline{r}=r+J$ to
$\overline{r+I}=\left(  r+I\right)  +\left(  J/I\right)  $.

Let us consider the ring morphism $f^{\prime}$. By its construction, it sends
each residue class $u+\operatorname*{Ker}\left(  \pi_{J}^{\prime}\right)  $ to
$\pi_{J}^{\prime}\left(  u\right)  $. In other words, it satisfies%
\begin{equation}
f^{\prime}\left(  u+\operatorname*{Ker}\left(  \pi_{J}^{\prime}\right)
\right)  =\pi_{J}^{\prime}\left(  u\right)  \label{pf.thm.3it.b.3}%
\end{equation}
for each $u\in R/I$. Hence, for each $r\in R$, we have%
\begin{align*}
f^{\prime}\left(  \left(  r+I\right)  +\operatorname*{Ker}\left(  \pi
_{J}^{\prime}\right)  \right)   &  =\pi_{J}^{\prime}\left(  r+I\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{pf.thm.3it.b.3}), applied to
}u=r+I\right) \\
&  =r+J\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{pf.thm.3it.1})}\right)  .
\end{align*}
In view of $\operatorname*{Ker}\left(  \pi_{J}^{\prime}\right)  =J/I$, we can
rewrite this as follows: For each $r\in R$, we have%
\begin{equation}
f^{\prime}\left(  \left(  r+I\right)  +\left(  J/I\right)  \right)  =r+J.
\label{pf.thm.3it.b.4}%
\end{equation}


Also, recall that the morphism $f^{\prime}$ (if we restrict its target to its
actual image $\pi_{J}^{\prime}\left(  R/I\right)  $) is a ring isomorphism
from $\left(  R/I\right)  /\operatorname*{Ker}\left(  \pi_{J}^{\prime}\right)
$ to $\pi_{J}^{\prime}\left(  R/I\right)  $. In view of $\operatorname*{Ker}%
\left(  \pi_{J}^{\prime}\right)  =J/I$ and $\pi_{J}^{\prime}\left(
R/I\right)  =R/J$, we can restate this as follows: The morphism $f^{\prime}$
(if we restrict its target to its actual image $R/J$) is a ring isomorphism
from $\left(  R/I\right)  /\left(  J/I\right)  $ to $R/J$.

Let $g:R/J\rightarrow\left(  R/I\right)  /\left(  J/I\right)  $ be the inverse
of this ring isomorphism. Thus, from (\ref{pf.thm.3it.b.4}), we see that%
\[
g\left(  r+J\right)  =\left(  r+I\right)  +\left(  J/I\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }r\in R.
\]
In other words, $g$ sends each residue class $r+J$ to $\left(  r+I\right)
+\left(  J/I\right)  $. Thus, we have found a ring isomorphism $R/J\rightarrow
\left(  R/I\right)  /\left(  J/I\right)  $ that sends each residue class $r+J$
to $\left(  r+I\right)  +\left(  J/I\right)  $ (namely, the isomorphism $g$).
This completes the solution to part \textbf{(b)} of the exercise.

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

\section{Exercise 9}

\subsection{Problem}

Let $R$ be a ring. Let $S$ be a subring of $R$. Let $I$ be an ideal of $R$.
Define $S + I$ to be the subset $\left\{  s + i \mid s \in S \text{ and } i
\in I \right\}  $ of $R$.

Prove the following:

\begin{itemize}
\item[\textbf{(a)}] This subset $S + I$ is a subring of $R$.

\item[\textbf{(b)}] The set $I$ is an ideal of the ring $S + I$.

\item[\textbf{(c)}] The set $S \cap I$ is an ideal of the ring $S$.

\item[\textbf{(d)}] We have $\left(  S + I \right)  / I \cong S / \left(  S
\cap I \right)  $ (as rings). More concretely, there is a ring isomorphism $S
/ \left(  S \cap I \right)  \to\left(  S + I \right)  / I$ that sends each
residue class $\overline{s} = s + \left(  S \cap I \right)  $ to $\overline{s}
= s + I$.
\end{itemize}

\subsection{Remark}

This is known as the \emph{Second Isomorphism Theorem for rings}.

For an example, we can let

\begin{itemize}
\item $R$ be the polynomial ring $\mathbb{Q}\left[  x \right]  $ of all
univariate polynomials with rational coefficients;

\item $I = \left\{  a_{2} x^{2} + a_{3} x^{3} + \cdots+ a_{n} x^{n} \mid n
\geq0 \text{ and } a_{i} \in\mathbb{Q} \right\}  $ be the ideal consisting of
all polynomials divisible by $x^{2}$ (that is, all polynomials whose $x^{0}%
$-coefficient and $x^{1}$-coefficient are $0$);

\item $S$ be the subring $\mathbb{Q}$ of $R$ (which consists of all constant polynomials).
\end{itemize}

Then, $S + I = \left\{  a_{0} + a_{2} x^{2} + a_{3} x^{3} + \cdots+ a_{n}
x^{n} \mid n \geq0 \text{ and } a_{i} \in\mathbb{Q} \right\}  $ is the set of
all polynomials whose $x^{1}$-coefficient is $0$. This is indeed a subring of
$R$, as we have seen in Lecture 6 (where we have used this subring to find an
irreducible element that is not prime).

\subsection{Solution}

...

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

\section{Exercise 10}

\subsection{Problem}

\begin{itemize}
\item[\textbf{(a)}] Let $R$ be a commutative ring, and let $u$ and $n$ be two
nonnegative integers. Let $x, y \in R$ be two elements such that $x - y \in
uR$. (Here, $uR := \left\{  ur \mid r \in R \right\}  $; this is a principal
ideal of $R$, since $uR = \left(  u1_{R} \right)  R$.)

Prove that
\[
x^{n} - y^{n} \in guR, \qquad\text{where } g = \gcd\left(  n, u \right)  .
\]


\item[\textbf{(b)}] Let $\left(  f_{0}, f_{1}, f_{2}, \ldots\right)  $ be the
Fibonacci sequence, defined as in Exercise 6 on homework set \#1. Prove that
\[
\gcd\left(  n, f_{d} \right)  \cdot f_{d} \mid f_{dn} \qquad\text{for any } d,
n \in\mathbb{N}.
\]

\end{itemize}

[\textbf{Hint:} For part \textbf{(a)}, write $x^{n} - y^{n}$ as $\left(  x-y
\right)  \left(  x^{n-1} + x^{n-2}y + \cdots+ y^{n-1} \right)  $, and show
that the second factor belongs to $gR$. For part \textbf{(b)}, define the
matrices $A$ and $B$ and the commutative ring $\mathcal{F}$ as in Exercise 6
on homework set \#1, and apply part \textbf{(a)} to $x = A^{d}$ and $y =
B^{d}$ and $u = f_{d}$.]

\subsection{Solution}

\textbf{(a)} Let $g=\gcd\left(  n,u\right)  $. Thus, $g=\gcd\left(
n,u\right)  \mid u$ and $g=\gcd\left(  n,u\right)  \mid n$. From $g\mid u$, we
can easily obtain $uR\subseteq gR$\ \ \ \ \footnote{\textit{Proof.} Let $a\in
uR$. Thus, $a=ur$ for some $r\in R$. Consider this $r$. Now, $g\mid u$, so
that $u=gc$ for some $c\in\mathbb{Z}$. Consider this $c$. We have
$a=\underbrace{u}_{=gc}r=g\underbrace{cr}_{\in R}\in gR$.
\par
Forget that we fixed $a$. We thus have shown that $a\in gR$ for each $a\in
uR$. In other words, $uR\subseteq gR$.}. Similarly, from $g\mid n$, we obtain
$nR\subseteq gR$.

Now, $x-y\in uR\subseteq gR$. Therefore, we have $\overline{x}=\overline{y}$
in the ring $R/gR$. Also, the map $R\rightarrow R/gR,\ a\mapsto\overline{a}$
is a ring morphism (indeed, this map is the canonical projection from $R$ to
$R/gR$), and thus preserves finite sums and powers. Hence, in $R/gR$, we have%
\begin{align}
\overline{x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}}  &  =\overline{x}%
^{n-1}+\overline{x}^{n-2}\overline{y}+\cdots+\overline{x}\,\overline{y}%
^{n-2}+\overline{y}^{n-1}\nonumber\\
&  =\sum_{k=0}^{n-1}\underbrace{\overline{x}^{n-1-k}\overline{y}^{k}%
}_{\substack{=\overline{y}^{n-1-k}\overline{y}^{k}\\\text{(since }\overline
{x}=\overline{y}\text{)}}}=\sum_{k=0}^{n-1}\underbrace{\overline{y}%
^{n-1-k}\overline{y}^{k}}_{=\overline{y}^{n-1}}=\sum_{k=0}^{n-1}\overline
{y}^{n-1}\nonumber\\
&  =n\overline{y}^{n-1}=\overline{ny^{n-1}} \label{sol.fib.lifting1.a.1}%
\end{align}
(again because the map $R\rightarrow R/gR,\ a\mapsto\overline{a}$ is a ring
morphism). However, $n\underbrace{y^{n-1}}_{\in R}\in nR\subseteq gR$, so that
$\overline{ny^{n-1}}=0_{R/gR}$ in the ring $R/gR$. Hence,
\eqref{sol.fib.lifting1.a.1} becomes
\[
\overline{x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}}=\overline{ny^{n-1}%
}=0_{R/gR}.
\]
In other words, $x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}\in gR$. In other
words, there exists some $r\in R$ such that
\[
x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}=gr.
\]
Consider this $r$.

Also, there exists some $s\in R$ such that
\[
x-y=us
\]
(since $x-y\in uR$). Consider this $s$.

Now, $xy=yx$ (since $R$ is commutative). Hence, a well-known formula says that%
\[
x^{k}-y^{k}=\left(  x-y\right)  \left(  x^{k-1}+x^{k-2}y+\cdots+xy^{k-2}%
+y^{k-1}\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }k\in\mathbb{N}.
\]
Applying this to $k=n$, we find%
\begin{align*}
x^{n}-y^{n}  &  =\underbrace{\left(  x-y\right)  }_{=us}\underbrace{\left(
x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}\right)  }_{=gr}\\
&  =\left(  us\right)  \left(  gr\right)  =ug\cdot\underbrace{sr}_{\in R}%
\in\underbrace{ug}_{=gu}R=guR.
\end{align*}
This solves part \textbf{(a)} of the exercise.

\bigskip

\textbf{(b)} Define the matrices $A,B\in\mathcal{F}$ and the commutative ring
$\mathcal{F}$ as in Exercise 6 on homework set \#1. (Recall that $A=%
\begin{pmatrix}
0 & 1\\
1 & 1
\end{pmatrix}
\in\mathbb{Z}^{2\times2}$ and $B=I_{2}-A\in\mathbb{Z}^{2\times2}$ and
$\mathcal{F}=\left\{  aA+bI_{2}\mid a,b\in\mathbb{Z}\right\}  \subseteq
\mathbb{Z}^{2\times2}$.)

We know that $A,B\in\mathcal{F}$ and thus $A-B\in\mathcal{F}$ (since
$\mathcal{F}$ is a subring of $\mathbb{Z}^{2\times2}$). Furthermore, Exercise
6 \textbf{(f)} on homework set \#1 says that%
\begin{equation}
A^{n}-B^{n}=f_{n}\left(  A-B\right)  \ \ \ \ \ \ \ \ \ \ \text{for all }%
n\in\mathbb{N}. \label{sol.fib.lifting1.a.2}%
\end{equation}


Now, let $d,n\in\mathbb{N}$. Set $g=\gcd\left(  n,f_{d}\right)  $. Then,
\eqref{sol.fib.lifting1.a.2} (applied to $d$ instead of $n$) yields%
\[
A^{d}-B^{d}=f_{d}\underbrace{\left(  A-B\right)  }_{\in\mathcal{F}}\in
f_{d}\mathcal{F}.
\]
Hence, part \textbf{(a)} of the present exercise (applied to $R=\mathcal{F}$
and $x=A^{d}$ and $y=B^{d}$ and $u=f_{d}$) yields%
\[
\left(  A^{d}\right)  ^{n}-\left(  B^{d}\right)  ^{n}\in gf_{d}\mathcal{F}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }g=\gcd\left(  n,f_{d}\right)
\right)  .
\]
In view of
\[
\underbrace{\left(  A^{d}\right)  ^{n}}_{=A^{dn}}-\underbrace{\left(
B^{d}\right)  ^{n}}_{=B^{dn}}=A^{dn}-B^{dn}=f_{dn}\left(  A-B\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by \eqref{sol.fib.lifting1.a.2}, applied to
}dn\text{ instead of }n\right)  ,
\]
this rewrites as%
\[
f_{dn}\left(  A-B\right)  \in gf_{d}\mathcal{F}.
\]
In other words, there exists a matrix $\gamma\in\mathcal{F}$ such that
\begin{equation}
f_{dn}\left(  A-B\right)  =gf_{d}\gamma\label{sol.fib.lifting1.a.3}%
\end{equation}
(by the definition of $gf_{d}\mathcal{F}$). Consider this $\gamma$.

Since matrices are scaled entrywise, we have%
\begin{align}
&  \left(  \text{the }\left(  2,2\right)  \text{-th entry of the matrix
}f_{dn}\left(  A-B\right)  \right) \nonumber\\
&  =f_{dn}\cdot\underbrace{\left(  \text{the }\left(  2,2\right)  \text{-th
entry of the matrix }A-B\right)  }_{\substack{=1\\\text{(this follows from a
straightforward computation)}}}=f_{dn}. \label{sol.fib.lifting1.a.5}%
\end{align}
On the other hand, $\gamma$ is a $2\times2$-matrix with integer entries (since
$\gamma\in\mathcal{F}\subseteq\mathbb{Z}^{2\times2}$). Hence, each entry of
$\gamma$ is an integer, i.e., belongs to $\mathbb{Z}$. Thus, in particular,%
\[
\left(  \text{the }\left(  2,2\right)  \text{-th entry of the matrix }%
\gamma\right)  \in\mathbb{Z}.
\]
Now, \eqref{sol.fib.lifting1.a.5} yields%
\begin{align*}
f_{dn}  &  =\left(  \text{the }\left(  2,2\right)  \text{-th entry of the
matrix }f_{dn}\left(  A-B\right)  \right) \\
&  =\left(  \text{the }\left(  2,2\right)  \text{-th entry of the matrix
}gf_{d}\gamma\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
\eqref{sol.fib.lifting1.a.3}}\right) \\
&  =gf_{d}\cdot\left(  \text{the }\left(  2,2\right)  \text{-th entry of the
matrix }\gamma\right)
\end{align*}
(since matrices are scaled entrywise). This yields that $gf_{d}\mid f_{dn}$
(in the classical sense of divisibility of integers), because we know that
$\left(  \text{the }\left(  2,2\right)  \text{-th entry of the matrix }%
\gamma\right)  \in\mathbb{Z}$. In other words, $\gcd\left(  n,f_{d}\right)
\cdot f_{d}\mid f_{dn}$ (since $g=\gcd\left(  n,f_{d}\right)  $). This solves
part \textbf{(b)} of the exercise.

\rule{\linewidth}{0.3pt} \\[0.4cm]

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[19s]{19s}Darij Grinberg, \textit{Introduction to Modern Algebra (UMN
Spring 2019 Math 4281 notes)}, 29 June 2019.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf}

\bibitem[DF]{DF}David S. Dummit, Richard M. Foote, \textit{Abstract Algebra},
3rd edition, Wiley 2004.

\bibitem[Grinbe15]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 15 September 2022.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2022-09-15c} .
\end{thebibliography}


\end{document}