\documentclass[%
version=last,%
a5paper,
10pt,%
%headings=small,%
bibliography=totoc,%
index=totoc,%
twoside,%
cleardoublepage=empty,%
%open=any,%
%draft=false,%
draft=true,%
%DIV=classic,%
DIV=10,%
%DIV=12,%
headinclude=true,%
pagesize]%
{scrartcl}

\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}
\usepackage{amsmath,amsthm,amssymb,upgreek}

\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\divides}{\mid}
\renewcommand{\theequation}{\fnsymbol{equation}}

\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem*{bonus}{Bonus}
\theoremstyle{remark}

\newtheorem*{solution}{Solution}
\usepackage{verbatim}
%\let\solution=\comment
%\let\endsolution=\endcomment

\pagestyle{empty}

\begin{document}
 MSGS\"U, MAT 221, S\i nav, 10 Kas\i m 2014, Saat 13:00, David Pierce.
\emph{Sadece 4 soruyu cevaplay\i n.}

%\noindent 
As in class, $\N$ is the set $\{1,2,3,\dots\}$ 
of \textbf{natural numbers,}
and $x'$ is the \textbf{successor} of $x$, so $1'=2$, $2'=3$, and so on.
We also let $\upomega=\{0\}\cup\N$ and $0'=1$.


\begin{problem}
For a given value of $n$ in $\N$,
let $\bar x$ denote the congruence-class of $x$ \emph{modulo} $n$,
and let $\Z_n=\{\bar x\colon x\in\N\}=\{\bar 1,\dots,\bar n\}$.
If $\overline{x'}=\overline{y'}$, then $\bar x=\bar y$.
Therefore we can define
%\begin{equation*}
$\bar x\;'=\overline{x'}$.
%\end{equation*}
The structure $(\Z_n,\bar 1,{}')$ allows proofs by induction.
We have shown
that addition and multiplication on $\Z_n$ can be defined recursively by
\begin{align*}
  \bar x+\bar 1&=\bar x\;',&\bar x+\bar y\;'&=(\bar x+\bar y)\;',\\
  \bar x\cdot\bar 1&=\bar x,&\bar x\cdot\bar y\;'&=\bar x\cdot\bar y+\bar x.
\end{align*}
\begin{enumerate}[(a)]
\item 
If $n=6$, show that there is an operation on $\Z_n$ given by
\begin{align}\label{*}
  \bar x^{\bar 1}&=\bar x,&\bar x^{\bar y'}&=\bar x^{\bar y}\cdot\bar x.
\end{align}
It is enough to fill out the table [in the solution].
\begin{comment}
  

$%\renewcommand{\arraystretch}{1.5}
\begin{array}{|*8{c|}}\hline
\multicolumn{2}{|c|}{}&\multicolumn{6}{c|}{y}\\\cline{3-8}
\multicolumn{2}{|c|}{\raisebox{1.5ex}[0pt]{$\bar x^{\bar y}$}}&1&2&3&4&5&6\\\hline
&1&&&&&&\\\cline{2-8}
&2&&&&&&\\\cline{2-8}
&3&&&&&&\\\cline{2-8}
\raisebox{1.5ex}[0pt]{$x$}&4&&&&&&\\\cline{2-8}
&5&&&&&&\\\cline{2-8}
%&6&\phantom{xxx}&\phantom{xxx}&\phantom{xxx}&\phantom{xxx}&\phantom{xxx}&\phantom{xxx}\\\hline
&6&&&&&&\\\hline
\end{array}$.


\end{comment}
\item
If $n=3$, show that there is \emph{no} operation on $\Z_n$ as in \eqref{*}.
\end{enumerate}
\end{problem}

\begin{solution}\mbox{}
  \begin{enumerate}[(a)]
  \item 
$\begin{array}{|*8{c|}}\hline
\multicolumn{2}{|c|}{}&\multicolumn{6}{c|}{y}\\\cline{3-8}
\multicolumn{2}{|c|}{\raisebox{1.5ex}[0pt]{$\bar x^{\bar y}$}}&1&2&3&4&5&6\\\hline
&1&1&1&1&1&1&1\\\cline{2-8}
&2&2&4&2&4&2&4\\\cline{2-8}
&3&3&3&3&3&3&3\\\cline{2-8}
\raisebox{1.5ex}[0pt]{$x$}&4&4&4&4&4&4&4\\\cline{2-8}
&5&5&2&5&2&5&2\\\cline{2-8}
&6&6&6&6&6&6&6\\\hline
\end{array}$
\hfill
    \begin{minipage}{0.45\textwidth}
    From the table it should be clear that, \emph{modulo} $6$,
      \begin{equation*}
        a\equiv b\implies x^a\equiv x^b.
      \end{equation*}
    \end{minipage}
\item
Using \eqref{*}, we obtain
$\bar 2^{\bar 1}=\bar 2$, $\bar 2^{\bar 2}=\bar 4=\bar 1$,
$\bar 2^{\bar 3}=\bar 2$, so $\bar 2^{\bar 4}=\bar 1$,
so $\bar 2^{\bar 1}\neq\bar 2^{\bar 4}$,
although $\bar 1=\bar 4$.
  \end{enumerate}
\end{solution}

\begin{problem}
  Using only the recursive definition of addition on $\N$ and induction,
prove that addition is associative.
\end{problem}

\begin{solution}
We want to show
$x+(y+z)=(x+y)+z$.
  \begin{compactenum}
    \item
  By the recursive definition of addition
(namely $x+1=x'$ and $x+y'=(x+y)'$), we have
  \begin{equation*}
    x+(y+1)=x+y'=(x+y)'=(x+y)+1,
  \end{equation*}
so the claim is true when $z=1$.
\item
Suppose the claim is true when $z=t$.  Then
\begin{align*}
  x+(y+t')
&=x+(y+t)'&&\text{[def'n of $+$]}\\
&=(x+(y+t))'&&\text{[def'n of $+$]}\\
&=((x+y)+t)'&&\text{[inductive hypothesis]}\\
&=(x+y)+t',&&\text{[def'n of $+$]}
\end{align*}
so the claim is true when $z=t'$.
  \end{compactenum}
By induction, the claim holds for all $z$ in $\N$
(for all $x$ and $y$ in $\N$).
\end{solution}

\begin{problem}
We know $2\cdot\displaystyle\sum_{k=1}^nk=n\cdot(n+1)$.  
For all $n$ in $\N$, prove
\begin{equation*}
\left(\displaystyle\sum_{k=1}^nk\right)^2=  \displaystyle\sum_{k=1}^nk^3.
\end{equation*}
\end{problem}

\begin{solution}
  The claim is obvious when $n=1$.
Suppose it is true when $n=m$.  Then
\begin{multline*}
\left(\sum_{k=1}^{m+1}k\right)^2
=\left(\sum_{k=1}^mk\right)^2+2\cdot\sum_{k=1}^mk\cdot(n+1)+(n+1)^2\\
=\sum_{k=1}^nk^3+n\cdot(n+1)^2+(n+1)^2
=\sum_{k=1}^nk^3+(n+1)^3
=\sum_{k=1}^{n+1}k^3.
\end{multline*}
\end{solution}

\begin{problem}
We can define the so-called binomial coefficients recursively by
  \begin{align*}
  \binom 00&=1,&\binom 0{k+1}&=0,\\
\binom{n+1}0&=1,&\binom{n+1}{k+1}&=\binom nk+\binom n{k+1}.
\end{align*}
Using only this definition, and induction,
show that, for all $n$ in $\upomega$,
\begin{equation*}
\displaystyle\sum_{k=0}^n\binom nk=2^n.
\end{equation*}
\end{problem}

\begin{solution}
  The claim is obvious when $n=0$.
Suppose it is true when $n=m$.  Then
\begin{multline*}
  \sum_{k=0}^{m+1}\binom{m+1}k
%=\binom{m+1}0+\binom{m+1}1+\dots+\binom{m+1}{m+1}\\
%=\binom{m+1}0+\left(\binom m0+\binom m1\right)+\dots+\left(\binom mm+\binom m{m+1}\right)\\
=\binom{m+1}0+\sum_{k=0}^m\binom{m+1}{k+1}\\
=1+\sum_{k=0}^m\left(\binom mk+\binom m{k+1}\right)\\
=\sum_{k=0}^m\binom mk+\sum_{k=0}^{m+1}\binom mk\\
=\sum_{k=0}^m\binom mk+\sum_{k=0}^m\binom mk
=2\cdot 2^m=2^{m+1}
\end{multline*}
(since $\binom{m+1}0=1=\binom m0$ and $\binom m{m+1}=0$).
Therefore, by induction, the claim is true for all $n$ in $\upomega$.
(We do not have $\binom m{m+1}=0$ immediately from the definition,
but can prove by induction that $\binom mn=0$ when $n>m$.)
\end{solution}

\begin{problem}
Let $d$ be the greatest common divisor of $385$ and $168$.
  \begin{enumerate}[(a)]
  \item 
Find $d$.
\item
Find a solution from $\N$ of one of the equations
\begin{align*}
  385x&=168y+d,&
168x&=365y+d.
\end{align*}
  \end{enumerate}
\end{problem}

\begin{solution}\mbox{}
  \begin{enumerate}[(a)]
  \item 
Since
\begin{align*}
   385&=168\cdot2+49\\
168&=49\cdot3+21\\
49&=21\cdot2+7
\end{align*}
and $7\divides 21$, we conclude $\gcd(385,168)=7$.
\item
From the previous computations,
\begin{align*}
  7
&=49-21\cdot2\\
&=49-(168-49\cdot3)\cdot2\\
&=49\cdot7-168\cdot2\\
&=(385-168\cdot2)\cdot7-168\cdot2\\
&=385\cdot7-168\cdot16.
\end{align*}
Thus $385\cdot7=168\cdot16+7$.
  \end{enumerate}
\end{solution}
\vfill
\end{document}