\documentclass[12pt,a4paper,twoside]{article}
\usepackage{amsmath,amssymb,amsthm}
%\usepackage[headings]{fullpage}
\usepackage{fullpage}
\usepackage{hfoldsty}
%\usepackage[mathscr]{euscript}
\usepackage{paralist}
%\setlength{\parindent}{0pt}

\newtheorem{problem}{Problem}

\theoremstyle{definition}
\newtheorem*{solution}{Solution}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{\theenumi.}
\renewcommand{\theequation}{\fnsymbol{equation}}
\newcommand{\included}{\subseteq}
\newcommand{\nincluded}{\nsubseteq}
\newcommand{\N}{\mathbb N}
\newcommand{\lcm}[1]{\operatorname{lcm}(#1)}

\renewcommand{\emptyset}{\varnothing}
\renewcommand{\leq}{\leqslant}
\newcommand{\rem}[1]{\operatorname{rem}(#1)}
\usepackage{bm}
\usepackage{upgreek}
\newcommand{\vnn}{\upomega}
\newcommand{\divides}{\mid}
\newcommand{\ndivides}{\nmid}

\begin{document}
\title{Math 365, 2010, Exam 1 \emph{solutions}}
\author{David Pierce}
\date{Monday, November 8, 2010}
\maketitle
\thispagestyle{empty}

The solutions to Problems 1 and 6, and especially the remarks on the
problems, were revised on November 25, 2010. 

\begin{problem}
Let $\vnn=\{0,1,2,\dots\}$.  All variables in this problem range over
$\vnn$.  Given $a$ and $b$ such that $a\neq0$, we define 
\begin{equation*}
\rem{b,a}=r,
\end{equation*}
if $b=ax+r$ for some $x$, and $r<a$.
\begin{enumerate}
\item
Prove $\rem{a+b,n}=\rem{\rem{a,n}+\rem{b,n},n}$.
\item
Prove $\rem{ab,n}=\rem{\rem{a,n}\cdot\rem{b,n},n}$.
\end{enumerate}
\end{problem}

\begin{solution}
\begin{asparaenum}
\item
For $\rem{c,n}$, write $c'$.  Then for some $x$, $y$, and $z$ in
$\vnn$, we have
\begin{align*}
  a&=nx+a',&
b&=ny+b',&
a'+b'&=nz+(a'+b')',
\end{align*}
hence $a+b=n(x+y+z)+(a'+b')'$.
Since $(a'+b')'<n$, 
we have
\begin{equation*}
(a+b)'=(a'+b')'
\end{equation*}
as desired.
\item
With the same notation, for some $w$ in $\vnn$ we have
\begin{equation*}
  a'\cdot b'=nw+(a'\cdot b')',
\end{equation*}
so for some $u$ in $\vnn$, we have
$ab=nu+a'\cdot b'=n(w+u)+(a'\cdot b')'$,
and therefore (since $(a'\cdot b')'<n$) we have 
\begin{equation*}
(ab)'=(a'\cdot b')'
\end{equation*}
as desired.
\end{asparaenum}
\end{solution}

\begin{remark}
Books VII, VIII, and IX of Euclid's \emph{Elements} develop some of
the theory of what we would call the positive integers.  If we allow also
a zero, but not negative numbers, then we could define
\begin{equation*}
  a\equiv b\pmod n\iff \rem{a,n}=\rem{b,n}.
\end{equation*}
This problem then could be used to establish the basic facts about
congruence. 
\end{remark}

\begin{remark}
A number of students used the arrow ``$\Rightarrow$'' in their
proofs.  Such usage is a bad habit, albeit a common one, even among
teachers.  Indeed, I learned this bad habit from somebody who was
otherwise one of my best teachers.  Later I unlearned the habit.

In logic, the
expression $A\Rightarrow B$ means
\begin{quote}
If $A$ is true, then $B$ is
true.
\end{quote}
One rarely wants to say this in proofs.  Rather, one wants to say
things like
\begin{quote}
$A$ is true, and therefore $B$ is true.
\end{quote}
If this is what you want to say, then you should just say it in words.

In the expression ``$A\Rightarrow B$'', the arrow is a
verb, usually read as ``implies''.  When somebody writes the arrow in
a proof, the intended meaning seems usually to be that of
``\emph{which} implies'' or ``\emph{and this} implies''.  But the
arrow should not be loaded up with these extra meanings.

One student used the arrow in place of the equals sign
``$=$''.  This usage must definitely be avoided.

Another practice that should be avoided is drawing arrows to direct
the reader's eye.  It should be possible to read a proof left to
right, top to bottom, in the usual fashion.  If you need to refer to
something that came before, then just say so.  

It is true that, when I
grade papers, I may use arrows.  This is in part because, when you see
your paper, I am there to explain what I meant by the arrow, if this
is necessary.  But what \emph{you} write on exam should make sense
without need for additional explanation by you.  

If I ask you to prove
a claim, I already know the claim is true.  The point is not to
convince me that the claim is true, or even to convince me that
\emph{you} know the claim is true.  The point is to write a proof of
the claim.  The point is to write the sort of thing that is found in
research articles and books of mathematics, often labelled with the
word \emph{Proof.}
\end{remark}

\begin{problem}
Find integers $k$ and $\ell$, both greater than $1$, such that, for
all positive integers~$n$, 
\begin{equation*}
k\divides 1965^{10n}+\ell.
\end{equation*}
\end{problem}

\begin{solution}
  Since $1965^{10n}$ is odd, we can let \fbox{$\ell=3$, $k=2$.}
\end{solution}

\begin{remark}
This problem is based on Exercise 6.
  As it is stated, the problem has many solutions.  
  \begin{compactenum}[(i)]
    \item
The solution given here
  is a special case of letting
 $k$ be any number such that $1965\equiv 1\pmod k$, and
  then letting $\ell=2k-1$ (or $k-1$ if $k>2$).  
\item
We could also let $\ell$ be
  a factor of $1965$, and then let $k$ be a factor of $\ell$.  
\item
Finally, since $11\ndivides 1965$, we have by Fermat
  $1965^{10}\equiv1\pmod{11}$, so we could let $k=11$ and $\ell=10$.
  \end{compactenum}
\end{remark}

\begin{problem}
Find two positive integers $a$ and $b$ such that, for all integers $m$
and $n$, the integer $am-bn$ is a solution of the congruences 
\begin{align*}
x&\equiv m\pmod{999},&
x\equiv n\pmod{1001}.
\end{align*}
\end{problem}

\begin{solution}
A solution of the congruences takes the form
\begin{equation*}
  x\equiv m\cdot 1001s+n\cdot 999t\pmod{999\cdot 1001},
\end{equation*}
where $1001s\equiv1\pmod{999}$ and $999t\equiv
1\pmod{1001}$.  So we want
\begin{align*}
  2s&\equiv 1,&s&\equiv 500\pmod{999},&
-2t&\equiv1,&t&\equiv500\pmod{1001}.
\end{align*}
Then the solution to the original congruences is
\begin{equation*}
  x\equiv m\cdot 1001\cdot 500+n\cdot 999\cdot 500
\equiv 1001\cdot 500m-999\cdot 501n\pmod{999\cdot 1001}.
\end{equation*}
So we can let
\fbox{$a=1001\cdot500$, $b=999\cdot 501$.}
\end{solution}

  \begin{remark}
This is just a Chinese Remainder Theorem problem with letters instead
of numbers.    
  \end{remark}

\begin{problem}
Letting  $n=\sum_{j=1}^{408}j$, find an integer $k$ such that $0\leq
k<409$ and 
\begin{equation*}
408!\equiv k\pmod n.
\end{equation*}
\end{problem}

\begin{solution}
We have $n=409\cdot 408/2$; also $409$ is prime, so by Wilson's
Theorem $408!\equiv-1\pmod{409}$.  Then $408!\equiv 408$ \emph{modulo}
both $409$ and $408$, hence \emph{modulo} any divisor of the
least common multiple of these.  But $n$ is such a divisor.  Thus we
can let \fbox{$k=408$.}
\end{solution}

\begin{remark}
This problem is based on Exercise 49(a).  A number of
people argued as follows.
\begin{quote}
Since $408!\equiv-1\pod{409}$, we must
have $k\equiv-1\pod{409}$.  Since it is required that $0\leq k<409$,
it must be that $k=408$.
\end{quote}
But this argument does \emph{not} prove $408!\equiv408\pod n$.  Maybe
I made a mistake, and there is \emph{no} $k$ meeting the stated
conditions. 
\end{remark}

\begin{problem}
With justification, find an integer $n$, greater than $1$, such that,
for all integers $a$, 
\begin{equation*}
a^n\equiv a\pmod{1155}.
\end{equation*}
\end{problem}

\begin{solution}
  We have $1155=3\cdot 5\cdot 7\cdot 11$, and
  $\gcd(3-1,5-1,7-1,11-1)=\gcd(2,4,6,10)=60$.  Then we can let
  \fbox{$n=61$.}  Indeed, by Fermat,
  \begin{compactitem}
    \item
If $3\ndivides a$, then $a^2\equiv1\pod 3$, so $a^{60}\equiv1\pod3$.
    \item
If $5\ndivides a$, then $a^4\equiv1\pod 5$, so $a^{60}\equiv1\pod5$.
    \item
If $7\ndivides a$, then $a^6\equiv1\pod 7$, so $a^{60}\equiv1\pod7$.
    \item
If $11\ndivides a$, then $a^{10}\equiv1\pod{11}$, so $a^{60}\equiv1\pod{11}$.
  \end{compactitem}
Therefore, for all $a$, we have $a^{61}\equiv a$ \emph{modulo} any of
$3$, $5$, $7$, and $11$, hence \emph{modulo} their least common
multiple, which is $1155$.
\end{solution}

\begin{remark}
  This problem is related to Exercise 43 and our discussion of
  absolute pseudoprimes.
\end{remark}

\begin{problem}
Let $\N=\{1,2,3,\dots\}$.
Suppose all we know about this set is:
\begin{compactenum}[(i)]
\item
proofs by induction are possible;
\item
addition can be defined on $\N$, and it satisfies
\begin{align*}
x+y&=y+x,&x+(y+z)&=(x+y)+z;
\end{align*}
\item
multiplication can be defined by
\begin{align*}
x\cdot 1&=x,&x\cdot(y+1)&=x\cdot y+x.
\end{align*}
\end{compactenum}
Prove
\begin{equation*}
x\cdot y=y\cdot x.
\end{equation*}
\end{problem}

\begin{solution}
We use induction on $y$.  As the base step, we show $x\cdot 1=1\cdot
x$ for all $x$.  We do \emph{this} by induction:  Trivially, $1\cdot1=1\cdot 1$.
Suppose, as an inductive hypothesis, $x\cdot1=1\cdot x$ for some $x$.  Then
\begin{align*}
1\cdot(x+1)&=1\cdot x+1&&\text{[by definition of multiplication]}\\
&=x\cdot 1+1&&\text{[by inductive hypothesis]}\\
&=x+1&&\text{[by definition of multiplication]}\\
&=(x+1)\cdot 1.&&\text{[by definition of multiplication]}
\end{align*}
By induction then, $x\cdot1=1\cdot x$.

Next we assume $x\cdot y=y\cdot x$ for all $x$, for some $y$, and we prove
$x\cdot(y+1)=(y+1)\cdot x$.  We do \emph{this} by induction on $x$.
By what we have already shown, $1\cdot(y+1)=(y+1)\cdot1$.  Suppose, as
an inductive hypothesis, $x\cdot(y+1)=(y+1)\cdot x$ for some $x$.
Then
\begin{align*}
  (x+1)\cdot(y+1)
&=(x+1)\cdot y+x+1&&\text{[by definition of multiplication]}\\
&=y\cdot(x+1)+x+1&&\text{[by the first inductive hypothesis]}\\
&=y\cdot x+y+x+1&&\text{[by definition of multiplication]}\\
&=x\cdot y+x+y+1&&\text{[by the first inductive hypothesis]}\\
&=x\cdot(y+1)+y+1&&\text{[by definition of multiplication]}\\
&=(y+1)\cdot x+y+1&&\text{[by the second inductive hypothesis]}\\
&=(y+1)\cdot(x+1).&&\text{[by definition of multiplication]}
\end{align*}
This completes the proof that $x\cdot(y+1)=(y+1)\cdot x$ for all $x$.
\emph{This} completes the proof that $x\cdot y=y\cdot x$ for all $x$
and $y$.
\end{solution}

\begin{remark}
  This is part of Exercise 1.  I tried to write out a ``first
  generation'' proof: one you might write without thinking of how to
  break it into parts.  A proof that is easier to follow is perhaps the
  ``second generation'' proof that goes as follows (see Lemma A.3 and Theorem 
  A.3): First show
  \begin{equation}\label{eqn:x1}
  x\cdot1=1\cdot x
  \end{equation}
by induction on $x$, then show
  \begin{equation}\label{eqn:y+1}
    (y+1)\cdot x=y\cdot x+x
  \end{equation}
by induction on $x$,
  and finally show $x\cdot y=y\cdot x$ by induction on $x$.  In fact,
  almost all students
  just \emph{assumed} that~\eqref{eqn:x1} and~\eqref{eqn:y+1} were
  known; but they were \emph{not} among the propositions that the
  problem allowed you to use.
\end{remark}

\end{document}