\documentclass[11pt]{article} \usepackage[utf8]{inputenc} \usepackage{graphicx} \usepackage[margin=1in]{geometry} \usepackage{enumitem} \usepackage{amsmath, amssymb, amsthm} \usepackage{xcolor} % THEOREM ENVIRONMENTS \theoremstyle{definition} \newtheorem*{theorem}{{Theorem}} \newtheorem*{lemma}{{Lemma}} \newtheorem*{proposition}{{Proposition}} \newtheorem*{definition}{{Definition}} \newtheorem*{corollary}{{Corollary}} \newtheorem*{example}{{Example}} \newtheorem*{remark}{{Remark}} \newtheorem*{claim}{{Claim}} \newtheorem*{question}{{Question}} \theoremstyle{plain} \newtheorem*{reminder}{{\textit{Reminder}}} \newtheorem*{hint}{{\textit{Hint}}} % ENVIRONMENTS FOR CITING BOOK STATEMENTS \newcommand{\prop}[1]{\paragraph{Proposition #1}} \newcommand{\axm}[1]{\paragraph{Axiom #1}} \newcommand{\thm}[1]{\paragraph{Theorem #1}} % COMMANDS \newcommand{\solution}{{\color{blue} \textsc{\ \\ Solution.\ \ }}} \newcommand{\Z}{\mathbb{Z}} % the integers \newcommand{\N}{\mathbb{N}} % natural numbers \newcommand{\R}{\mathbb{R}} % real numbers \newcommand{\divides}{\ \vert \ } \newcommand{\st}{ \ : \ } % such that \newcommand{\inv}{^{-1}} % inverse \newcommand{\exheading}[1]{\section*{Exercise #1}} \newcounter{exnum} % \setcounter{exnum}{1} % default 0 start \newcommand{\exercise}{ \stepcounter{exnum} \exheading{\theexnum} } \newcommand{\bea}{\begin{enumerate}[label=(\alph*)]} \newcommand{\bei}{\begin{enumerate}[label=(\roman*)]} \newcommand{\ee}{\end{enumerate}} \renewcommand{\implies}{\Rightarrow} % shorter implies arrow \newcommand{\mz}[1]{{\color{magenta} #1}} % mz comments to self \title{MAT 108 PS05} \author{Melissa Zhang} \date{Due Monday, May 4, 2026 at 9:00 pm on Gradescope} \begin{document} \maketitle \section*{Instructions} There are three goals for this problem set: \begin{itemize} \item Maintain good mathematical writing form in your justifications even when you aren't explicitly asked to prove a given statement. \item Practice working with equivalence relations and equivalence classes. \item Gain familiarity with common examples of equivalence classes that inherit algebraic structure (``quotient rings''), such as $\Z/n\Z$. \item Understand better when and how to check ``well-definedness''. \end{itemize} \noindent Here are some reminders about best practices: \begin{itemize} \item You absolutely must write in full, connected English sentences. Whenever possible, do not start a sentence with mathematical symbols. Do not use symbols like $\implies$, $\forall$, $\exists$, $\therefore$, etc.\ (except when explicitly discussing statements about logic). \item Your solution must be \emph{neat}. You \textbf{will} be graded on style, which includes mathematical style and professionalism. \item It is your responsibility to mark where your solutions for each problem begins on Gradescope so that the TA and reader can properly grade your solutions. \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise \textbf{(Not graded)} Do you know the difference between the symbols $\in$ and $\subseteq$? Explain to yourself what the follow statements mean: \begin{itemize} \item $a \in P \in S$ \item $a \in P \subset S$ \item $A \subset P \in S$ \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise For each of the following relations, determine whether it is an equivalence relation. If it is, determine the equivalence classes. \bea \item On $\Z$, $x\sim y$ if $xy >0$. \item On $\Z- \{0\}$, $x \sim y$ if $x | y$ or $y | x$. \item On $\Z$, $x\sim y$ if $x = y$ or $x = -y$. \ee %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise For a moment, pretend we have already introduced the real numbers $\R$ that we work with all the time in calculus. Prove that the following are equivalence relations, and describe the equivalence classes geometrically. \bea \item On the plane $\R \times \R$, define $(x,y) \sim (v,w)$ if $x^2 + y^2 = v^2 + w^2$. \item On the \emph{punctured} plane $\R \times \R - \{0,0\}$, define $(x,y) \sim (v,w)$ if there exists a nonzero $r \in \R$ such that $(v,w) = (rx, ry)$. \ee %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise Prove that the multiplication operation \begin{align*} \cdot: \Z/n\Z \times \Z/n\Z & \to \Z/n\Z \\ ([a],[b]) & \mapsto [a\cdot b] \end{align*} on $\Z/n\Z$ is well-defined. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise Consider the set $\Z/7\Z$, equipped with the operations addition ($+$) and multiplication ($\cdot$). We also have division, defined as a function \begin{align*} \text{division}: \Z/7\Z \times (\Z/7\Z - \{[0]\}) & \to \Z/7\Z\\ (x,y) \mapsto x\cdot y\inv \end{align*} which you will be able to define after you've completed part (a) below. \begin{remark} For readability reasons, we will stop using the notation $[x]$ to represent the equivalence class of $x \in \Z$ under the ``mod 7" relation. In real life, mathematicians just write ``2" for $[2] \in \Z/7\Z$ if the context is clear. \end{remark} \begin{enumerate}[label={(\alph*)}] \item For each of the elements of $\Z/7\Z - \{0\}$, determine its (multiplicative) inverse. (Fill in the table provided.) \item Fill in the addition table provided below. \item Fill in the multiplication table provided below. \item An element $m \in \Z$ is called a \emph{square} if there exists some $n \in \Z$ such that $n\cdot n = m$. We can make the same definition in $\Z/7\Z$. Which elements of $\Z/7\Z - \{0\}$ are \emph{squares}? (Fill in the chart below.) \emph{($0$ is indeed a square, but it's extra special, so we consider it separately.)} \end{enumerate} This is an exploration problem. You don't need to write any proofs; just work out the calculations and fill in the tables like the ones below: \begin{enumerate}[label={(\alph*)}] \item % Inverse table: \begin{tabular}{|c|c|} \hline Element of $\Z/7\Z - \{0\}$ & Inverse element \\ \hline \hline 1 & \\\hline 2 & \\\hline 3 & \\\hline 4 & \\\hline 5 & \\ \hline 6 & \\ \hline \end{tabular} \item % Addition table: \begin{tabular}{|c|c c c c c c c |} \hline $+$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 0 & & & & & & & \\ 1 & & & & & & & \\ 2 & & & & & & & \\ 3 & & & & & & & \\ 4 & & & & & & & \\ 5 & & & & & & & \\ 6 & & & & & & & \\ \hline \end{tabular} \item % Multiplication table: \begin{tabular}{|c|c c c c c c c |} \hline $\cdot$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 0 & & & & & & & \\ 1 & & & & & & & \\ 2 & & & & & & & \\ 3 & & & & & & & \\ 4 & & & & & & & \\ 5 & & & & & & & \\ 6 & & & & & & & \\ \hline \end{tabular} \item % Squares: \begin{tabular}{|c|c|} \hline Squares: & \\ \hline Non-squares: & \\ \hline \end{tabular} \end{enumerate} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise Recall that $\Z[x]$ denotes the set of polynomials in the indeterminate variable $x$ with coefficients in the integers. (Also recall from precalculus that polynomial addition and multiplication are both commutative and associative, and satisfy the distributive property. There's no need to mention these terms in your solution to this exercise.) We define divisibility of polynomials similarly to how we defined it for integers: \begin{definition} For polynomials $f(x), p(x) \in \Z[x]$, we say $p(x)$ divides $f(x)$, and write $p(x) \divides f(x)$, if there exists some $q(x) \in \Z[x]$ such that $f(x) = p(x)q(x)$. \end{definition} We wish to define an algebraic object called $\Z[x]/(p(x))$ as the equivalence classes of the following equivalence relation: \[ f(x) \sim g(x) \qquad \text{if} \qquad p(x) \divides (f(x) - g(x)). \] \bea \item Prove that $\sim$ is an equivalence relation. \item For $p(x) = x^2$, determine the set of equivalence classes. Use set notation to explicitly write down each equivalence class. \item There are \emph{induced} addition and multiplication operations on $\Z[x]/(p(x))$; this means that the definition is inherited from addition in $\Z[x]$. Write down these two binary operations (as in Exercise 4). (No proof needed here.) \item Prove that addition and multiplication are both well-defined. \ee \end{document}