\documentclass[12pt]{article}
\usepackage[margin=0.5in,top=0.7in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath,amsthm,amsfonts}
\usepackage{tikz}
\usepackage{multirow}
\usepackage{substr}
\usepackage{pgfplots}
\makeatletter
\renewcommand*\env@matrix[1][*\c@MaxMatrixCols c]{%
\hskip -\arraycolsep
\let\@ifnextchar\new@ifnextchar
\array{#1}}
\makeatother
% Include "solution" in your filename to make sure the right mode is
% used below.
\IfSubStringInString{\detokenize{solution}}{\jobname}{%
% Solutions
\newcommand\qfill{}
\newcommand\qpage{}
\newcommand\qonly[1]{}
\newcommand\answer[1]{#1}
\newcommand\question[1]{{\em #1}}
}
{%
% Problems
\newcommand\qfill{\vfill}
\newcommand\qpage{\newpage}
\newcommand\qonly[1]{#1}
\newcommand\answer[1]{}
\newcommand\question[1]{#1}
}
\pagestyle{fancy}
\lhead{MATH 521--01}
\chead{Problem Set \#1\answer{ solutions}}
\rhead{}
\lfoot{}
\cfoot{\answer{Page \thepage\ of \pageref{LastPage}}}
\rfoot{due Thursday, September 4, 2014}
\begin{document}
\begin{enumerate}
\item \question{Prove that for every integer $n$, $n^3\equiv n\pmod 6$.}
\answer{
\begin{proof}
Since multiplication and addition are well-defined on the six
congruence classes modulo 6, all we need to do is show that
$n\cdot n\cdot n$ is congruent to $n$ within each of the
congruence classes. So,
\begin{align*}
\text{When $n\equiv 0\pmod 6$: }&n^3\equiv 0^3\equiv 0\equiv n\pmod 6\\
\text{When $n\equiv 1\pmod 6$: }&n^3\equiv 1^3\equiv 1\equiv n\pmod 6\\
\text{When $n\equiv 2\pmod 6$: }&n^3\equiv 2^3\equiv 8\equiv 2\equiv n\pmod 6\\
\text{When $n\equiv 3\pmod 6$: }&n^3\equiv 3^3\equiv 27\equiv 3\equiv n\pmod 6\\
\text{When $n\equiv 4\pmod 6$: }&n^3\equiv 4^3\equiv 64\equiv 4\equiv n\pmod 6\\
\text{When $n\equiv 5\pmod 6$: }&n^3\equiv 5^3\equiv 125\equiv 5\equiv n\pmod 6
\end{align*}
So in all 6 cases, $n^3\equiv n\pmod 6$.
\end{proof}
\begin{proof}[Alternative proof]
Note that $n^3-n=n(n-1)(n+1)$. At least one of $n$ or $n-1$ is
even, so $n(n-1)(n+1)$ is even. Also, exactly one of $n$, $n-1$,
or $n+1$ must be divisible by $3$, so $n(n-1)(n+1)$ is divisible
by 3. Since $n^3-n$ is divisible by both 2 and 3, it is
divisible by 6. And by definition, since $6\mid n^3-n$,
$n^3\equiv n\pmod 6$.
\end{proof}
\begin{proof}[Another alternative proof]
We can prove this for every non-negative integer by induction,
and then note that for every positive $n$, $(-n)^3=-n^3\equiv
-n$, so negative integers follow the same rule. Our inductive
proof starts with base case $0$; $0^3\equiv 0\pmod 6$. Now, let
us assume that for a given $n$, $n^3\equiv n\pmod 6$, and
proceed to prove that $(n+1)^3\equiv n+1\pmod 6$. We can prove
that $n^2+n$ is even by noting that it is always a sum of two
numbers of the same parity. Thus, $3(n^2+n)\equiv 0\pmod 6$, so
adding this to both sides of our inductive assumption:
\begin{align*}
n^3&\equiv n\pmod 6\\
n^3+3(n^2+n)&\equiv n+0\pmod 6\\
n^3+3n^2+3n+1&\equiv n+1\pmod 6\\
(n+1)^3&\equiv n+1\pmod 6
\end{align*}
\end{proof}
}
\item \question{Let us say that, for nonzero rational numbers $a$ and
$b$, $a\simeq b$ if $a$ and $b$ have the same denominator when
written in lowest terms. Explain why $\simeq$ is an equivalence
relation and describe its equivalence classes.}
\answer{
To prove reflexivity, let us consider an arbitrary nonzero
rational number $x$ which has the form $\frac pq$ when written in
lowest terms. Since $x$ has the same denominator as itself
(specifically: $q$), $x\simeq x$.
To prove symmetry, let us consider nonzero rationals $x$ and $y$
such that $x\simeq y$. Let $x$ have the form $\frac pq$ when
written in lowest terms. Since $x\simeq y$, $y$ has the same
denominator, so in lowest terms $y$ has the form $\frac{p'}q$ for
some (possibly different) $p'$. Since $y$ has the same denominator
as $x$ (specifically: $q$), $y\simeq x$.
To prove transitivity, let us consider nonzero rationals $x$, $y$,
and $z$ such that $x\simeq y$ and $y\simeq z$. Let $x$ have the
form $\frac{p_1}q$ when written in lowest terms. Since $x\simeq
y$, $y$ has the same denominator as $x$, so in lowest terms $y$
has the form $\frac{p_2}q$. Since $y\simeq z$, $z$ has the same
denominator as $y$, so $y$ has the form $\frac{p_3}q$. Since $x$
has the same denominator as $z$ (specifically: $q$), $x\simeq z$.
The equivalence classes group together all numbers with the same
denominator in lowest terms. For instance, the equivalence class
$[1]$ contains only nonzero integers:
\[[1]=\{\cdots,-5,-4,-3,-2,-1,1,2,3,4,5,\cdots\}\]
while the equivalence class $[\tfrac12]$ contains half-integers only:
\[[\tfrac12]=\{\cdots,\tfrac{-9}2,\tfrac{-7}2,\tfrac{-5}2,\tfrac{-3}2,\tfrac{-1}2,\tfrac{1}2,\tfrac{3}2,\tfrac{5}2,\tfrac{7}2,\tfrac{9}2,\cdots\}\]
and so forth; note that certain equivalence classes are a bit sparse:
\[[\tfrac16]=\{\cdots,\tfrac{-13}6,\tfrac{-11}6,\tfrac{-7}6,\tfrac{-5}6,\tfrac{-1}6,\tfrac{1}6,\tfrac{5}6,\tfrac{7}6,\tfrac{11}6,\tfrac{13}6,\cdots\}\]
In general, an archtypical equivalence class might have
representative element $\frac1k$ for any positive integer $k$, and
have elements given by the following rule:
\[[\tfrac1k]=\{\tfrac nk:n\in\mathbb Z,n\neq 0,\gcd(n,k)=1\}\]
}
\item \question{Prove that for every number $k$ there is a number $N$
such that all of the numbers $N+1, N+2, N+3, \cdots, N+k$
are composite.}
\answer{
\begin{proof}
We shall prove specifically that any $N>1$ such that $N\equiv
1\pmod{(k+1)}!$ satisfies this rule; we shall do this by induction
on $k$.
In the base case $k=1$, we are asserting that whenever $N\equiv
1\pmod 2$ and $N>1$, it is the case that $N+1$ is
composite. This is trivial because if $N\equiv 1\pmod 2$ then
$N+1$ is even; since $N>1$, $N+1>2$, and thus $N+1$ is
composite, as it is divisible by 2.
For our inductive step, we assume that for $N\equiv 1\pmod{k!}$
and $N>1$, all of $N+1, N+2,\ldots, N+(k-1)$ are composite. Now
we want to take some subset of this family of values of $N$ and
show that on them, $N+k$ is also composite. Let us specifically
try to engineer it to be the case that $N+k$ is divisible by
$k+1$ (and since $N>1$, it is not equal to $k+1$). In
particular, we want values of $N$ such that $N+k\equiv
0\pmod{k+1}$, or in other words, $N\equiv 1\pmod{k+1}$.
We thus can satisfy our desired rule on $N$ by simultaneously
satisfying the two congruences:
\begin{align*}
N&\equiv 1\pmod{k!}\\
N&\equiv 1\pmod{k+1}
\end{align*}
which is in fact true whenever $N\equiv1\pmod{(k+1)!}$,
completing our inductive step.
\end{proof}
\begin{proof}[Alternative proof]
An easy way to prove this result by example would be to let
$N=(k+1)!+1$. Then, note that for each $i\leq k$,
$N+i=(k+1)!+i+1$, and since $(k+1)!$ is divisible by $i+1$,
$(k+1)!+i+1$ is also divisible by $i+1$, so $N+i$ is divisible
by $i+1$ and thus nonprime.
\end{proof}
}
\item \question{Determine the symmetries of a rectangle which is not a
square; give each symmetry a name and produce a Cayley table.}
\answer{
A nonsquare rectangle is \emph{not} symmetric when rotated
clockwise or counterclockwise by $90^\circ$, or when reflected
across a diagonal, but will be symmetric under an 180-degree
rotation or a reflection across an axis bisecting an opposite pair
of sides. There are thus four symmetries. including the identity
transformation $I$, which is not pictured below, the vertical flip
$V$, the horizontal flip $H$, and the rotation $R$.
\begin{center}
\begin{tikzpicture}
\draw[thick] (-2,-1) rectangle (2,1);
\draw[green,dashed] (-2.25,0)--(2.25,0) node[right] {$V$};
\draw[red,dashed] (0,-1.25)--(0,1.25) node[above] {$H$};
\draw[blue,-stealth] (3,0) arc (0:180:3 and 2) node[below] {$R$};
\end{tikzpicture}
\end{center}
Now, to build a Cayley table, we will consider what results when
we perform the various actions in sequence; obviously any action
together with the identity transformation is unaffected, while
performing any action twice returns things to their original
state. Less obviously, performing both flips (in any order)
results in the same action as the rotation, and a flip with a
rotation is identical to the other flip. So our Cayley table is:
\begin{center}
\begin{tabular}{|c||c|c|c|c|}
\hline
&I&V&H&R\\\hline\hline
I&I&V&H&R\\\hline
V&V&I&R&H\\\hline
H&H&R&I&V\\\hline
R&R&H&V&I\\\hline
\end{tabular}
\end{center}
Incidentally, this is actually an Abelian group.}
\item \question{Describe the infinite group of symmetries of the
following infinitely long figure. Determine as many rules as you
can for multiplying the symmetries, and determine whether this
group is Abelian.
\begin{center}
\begin{tikzpicture}
\fill (-2,0) circle (0.05);
\fill (-1.5,0) circle (0.05);
\fill (-1,0) circle (0.05);
\draw[thick] (-0.5,0)--(6.5,0);
\draw[thick] (0,0)-- ++(-0.5,0.5);
\draw[thick] (1,0)-- ++(-0.5,-0.5);
\draw[thick] (2,0)-- ++(-0.5,0.5);
\draw[thick] (3,0)-- ++(-0.5,-0.5);
\draw[thick] (4,0)-- ++(-0.5,0.5);
\draw[thick] (5,0)-- ++(-0.5,-0.5);
\draw[thick] (6,0)-- ++(-0.5,0.5);
\fill (7,0) circle (0.05);
\fill (7.5,0) circle (0.05);
\fill (8,0) circle (0.05);
\answer{
\draw[green,|-stealth] (2,1)--(4,1);
\draw[green] (3,1) node[above] {$T$};
\draw[red,dashed] (0,1) arc (90:270:0.25 and 1);
\draw[red,-stealth] (0,-1) -- (1,-1) node[right] {$G$};
}
\end{tikzpicture}
\end{center}
}
\answer{This shape has two fundamental transformations: a
translation mapping each ``quill'' onto the next neighbor on the
same side, denoted in the image above by $T$, and a glide
reflection mapping each quill onto the next quill on the opposite
side, denoted in the image by $G$. Note that there is in fact an
\emph{infinite} family of transformations so described: not only
is there the transformation $T$, but also the result of performing
$T$ twice, called $T^2$, or three times, called $T^3$, etc. In
addition we could reverse $T$ and call it $T^{-1}$, or perform its
reverse several times, and so forth.
Note that $G$ can be combined with $T$ or with itself, but
performing $G$ twice maps a quill by simple transformation, so
$G^2=T$. We could thus say that every transfromation in here is
either $T^k$ or $GT^k$ for integer $k$, and we have the following
compositional rules:
\begin{align*}
T^aT^b&=T^{a+b}\\
(GT^a)(T^b)&=GT^{a+b}\\
(T^a)(GT^b)&=GT^{a+b}\\
(GT^a)(GT^b)&=T^{a+b+1}
\end{align*}
And note that this group \emph{is} Abelian.}
\end{enumerate}
\end{document}