\documentclass[%
version=last,%
a5paper,
10pt,%
%headings=small,%
twoside,%
reqno,%
parskip=half,%
%draft=false,%
draft=true,%
%DIV=classic,%
DIV=12,%
headinclude=false,%
%titlepage=true,%
pagesize]
{scrartcl}
%\documentclass[a4paper,12pt]{article}
%\usepackage[DIV=12]{typearea}
%\usepackage[hscale=0.8,vscale=0.9,centering]{geometry}

%\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
%\usepackage{pstricks}

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

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

%\theoremstyle{remark}
\newtheorem*{solution}{Solution}

%\let\solution\comment
%\let\endsolution\endcomment

%\newcommand{\myvspace}[1]{\vspace{#1}}
\newcommand{\myvspace}[1]{}

%\renewcommand{\vfill}{}

\newcommand{\divides}{\mid}
\newcommand{\ndivides}{\nmid}
\newcommand{\Z}{\mathbb Z}
\newcommand{\ord}[2][7]{\operatorname{ord}_{#1}(#2)}
\renewcommand{\setminus}{\smallsetminus}
\renewcommand{\leq}{\leqslant}
\renewcommand{\mod}[1]{(\operatorname{mod}#1)}

%\pagestyle{myheadings}
% \markboth{Mat 113 Sınav, 5 Kas\i m 2012}{Mat 113 Sınav, 5 Kas\i m 2012}   
\pagestyle{empty}

%\usepackage{fullpage}

\begin{document}
\title{MAT 221 exam solutions}
\date{January 10, 2013}
\author{David Pierce}
\publishers{%MAT 221, MSGS\"U\\
%\url{dpierce@msgsu.edu.tr}\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}
\maketitle

\begin{problem}
%What is wrong with the following argument?
Explain why the following argument is incorrect.
\begin{compactenum}
\item
All numbers are equal to one another.
\item
We shall prove this by showing by induction that, for all positive integers $n$, for every set of $n$ numbers, those numbers are all equal to one another.
\item
This is obviously true when $n=1$: if a set contains just one number, then all numbers in the set are equal to one another.
\item
Suppose the claim is true when $n=k$, so that for every set of $k$ numbers, those numbers are equal to one another.
\item
Let $A$ be a set of $k+1$ numbers.
\item
Suppose $b\in A$ and $c\in A$; we shall show $b=c$.
\item
Suppose $b\neq c$.
\item
Then $c\in A\setminus\{b\}$.
\item
By inductive hypothesis, all elements of $A\setminus\{b\}$ are equal to one another.
\item
Let $d\in A\setminus\{b\}$.
\item
Therefore $c=d$.
\item\label{wrong}
Similarly $b=d$.  (That is, $b\in A\setminus\{c\}$, so if $d\in A\setminus\{c\}$, we have $b=d$.)
\item
Therefore $b=c$.
\item
Thus all elements of $A$ are equal to one another.
\item
By induction, every set of $n$ numbers really contains only one number.
\end{compactenum}
\end{problem}

\begin{solution}
Step 12 is incorrect.  There is no similarity to step 11.  The
elements $b$ and $c$ of $A$ are not interchangeable with respect to
$d$.  By step 10, $d\in A\setminus\{b\}$; but we need not have $d\in
A\setminus\{c\}$.  In fact $d\notin A\setminus\{c\}$, since $d=c$.
(The argument in parentheses in step 12 is correct, but the hypothesis
$d\in A\setminus\{c\}$ is false, so the conclusion $b=d$ does not follow.) 
\end{solution}

\begin{problem}
The following prime factorizations will be useful:
\begin{align*}
280&=2^3\cdot5\cdot7,&
679&=7\cdot97.
\end{align*}
\begin{compactenum}[(a)]
\item
If the congruence
\begin{equation*}
280x\equiv a\pmod{679}
\end{equation*}
has at least one solution, how many solutions \emph{modulo} $679$ does it have?
\myvspace{4cm}
\begin{solution}
Since $\gcd(679,280)=7$, there are $7$ solutions, if there are any at all.
\end{solution}
\item\label{c}
Find all solutions of the linear congruence $40x\equiv14\pmod{97}$.  (Do not try to solve by trial and error; there is a clear method available to us.)
%\myvspace{15cm}
\begin{solution}
We have $\gcd(40,14)=2$ (and $2\ndivides97$); so we have to solve
\begin{equation*}
20x\equiv7\pmod{97}.
\end{equation*}
We invert $20$ \emph{modulo} $97$ by means of the Euclidean algorithm:
\begin{align*}
97&=20\cdot4+17,\\
20&=17\cdot1+3,\\
17&=3\cdot5+2,\\
 3&=2\cdot1+1,
\end{align*}
and then
\begin{align*}
1&=3-2=3-(17-3\cdot5)\\
&=3\cdot6-17=(20-17)\cdot6-17\\
&=20\cdot6-17\cdot7=20\cdot6-(97-20\cdot4)\cdot7\\
&=20\cdot34-97\cdot7.
\end{align*}
Thus
\begin{equation*}
x\equiv34\cdot7=238\equiv44\pmod{97}.
\end{equation*}
\end{solution}
\item
Find all solutions of the linear congruence $280x\equiv98\pmod{679}$.  (You may express these in terms of a solution to the congruence in part \eqref{c}.)
\begin{solution}
Since $98=7\cdot14$, the solutions of $280x\equiv98\pmod{679}$ are precisely the solutions of $40x\equiv14\pmod{97}$; but if $b$ is a solution of the latter, then the solutions of the former are expressed as
\begin{equation*}
x\equiv a,a+97,a+97\cdot2,\dots,a+97\cdot 6\pmod{679}.
\end{equation*}
In fact the solutions are 
\begin{equation*}
x\equiv44,141,238,335,432,529,626\pmod{679}.
\end{equation*}
\end{solution}
\end{compactenum}
\end{problem}

\begin{problem}
The number $2003$ is known to be a prime number.  
\begin{compactenum}[(a)]
\item
Solve $2x\equiv1\pmod{2003}$.
\myvspace{2cm}
\begin{solution}
$x\equiv1002\equiv-1001\pmod{2003}$.
\end{solution}
\item
Compute $2000!$ \emph{modulo} $2003$.  (We have a named theorem that is useful for this.)
\begin{solution}
By Wilson's Theorem,
\begin{equation*}
2002!\equiv-1\pmod{2003},
\end{equation*}
and therefore
\begin{equation*}
2000!\equiv\frac{2002!}{2002\cdot2001}\equiv\frac{-1}{-1\cdot-2}\equiv1001\pmod{2003}.
\end{equation*}
\end{solution}
\end{compactenum}
\end{problem}

\begin{problem}
\begin{compactenum}[(a)]
\item
Show that $3$ is a primitive root of $7$ by filling out the following table:
\begin{equation*}
\renewcommand{\arraystretch}{1.5}
\begin{array}{|r|*6{c|}l|}\hline
   k   &1&2&3&4&5&6&\mod{6}\\\hline
3^ k   &\phantom{999} &\phantom{999} &\phantom{999} &\phantom{999} &\phantom{999} &\phantom{999} &\mod{7}\\\hline
\end{array}
\end{equation*}
\begin{solution}
\begin{math}
\begin{array}{|r|*6{c|}l|}\hline
   k   & 1& 2& 3& 4& 5& 6&\mod{6}\\\hline
2^ k   & 3& 2&-1&-3&-2& 1&\mod{7}\\\hline
\end{array}
\end{math}
\end{solution}
\item\label{ord}
Fill out the following table.  (Recall that $\ord[p] a$ is the least non-negative exponent $b$ such that $a^b\equiv1\pmod{p}$.)
\begin{equation*}
\renewcommand{\arraystretch}{1.5}
\begin{array}{|r|*6{c|}l|}\hline
   k   &\phantom{999} &\phantom{999} &\phantom{999} &\phantom{999} &\phantom{999} &\phantom{999} &\mod{6}\\\hline
3^ k   &1&2&3&4&5&6&\mod{7}\\\hline
\ord{3^k}&&&&&&&\\\hline
\end{array}
\end{equation*}
\begin{solution}
\begin{math}
\begin{array}{|r|*6{c|}l|}\hline
         k & 0& 2& 1& 4& 5& 3&\mod{6}\\\hline
      3^ k & 1& 2& 3& 4& 5& 6&\mod{7}\\\hline
  \ord{3^k}& 1& 3& 6& 3& 6& 2&        \\\hline
\end{array}
\end{math}
\end{solution}
\item
Fill out the following table, in which $\upphi$ is Euler's phi-function.  (You can use this to check your work in \eqref{ord}, since for every divisor $d$ of $6$, the number of elements of $\Z_{7}{}^{\times}$ with order $d$ is precisely $\upphi(d)$.  Alternatively, if you are confident of your solution to \eqref{ord}, you can use that to fill out the table here.)
\begin{equation*}
\renewcommand{\arraystretch}{1.5}
\begin{array}{|r|*4{c|}}\hline
       d &1&2&3&6\\\hline
\upphi(d)&\phantom{999} &\phantom{999} &\phantom{999} &\phantom{999} \\\hline
\end{array}
\end{equation*}
\begin{solution}
\begin{math}
\begin{array}{|r*4{|c}|}\hline
       d &1&2&3&6\\\hline
\upphi(d)&1&1&2&2\\\hline
\end{array}
\end{math}
\end{solution}
\item
Solve the quadratic congruence
\begin{equation*}
x^2+8x+5\equiv0\pmod{19}.
\end{equation*}
Again, do not use trial and error; we have a clear method.  You may find needed square roots from the following table: and then you should make it clear how you do this.
\begin{equation*}
\begin{array}{|r|*9{c|}l|}\hline
   k   & 1& 2& 3& 4& 5& 6& 7& 8& 9&\mod{18}\\\hline
2^ k   & 2& 4& 8&-3&-6& 7&-5& 9&-1&\mod{19}\\\hline
2^{k+9}&-2&-4&-8& 3& 6&-7& 5&-9& 1&\mod{19}\\\hline
\end{array}
\end{equation*}
\begin{solution}
\begin{math}
x
\equiv\displaystyle\frac{-8\pm\sqrt{64-20}}2
\equiv\displaystyle\frac{-8\pm\surd6}2.
\end{math}
From the table, $6\equiv2^{14}$, so $\surd6\equiv\pm2^7\equiv\mp5$.  Therefore $x\equiv-4\pm10\cdot5
\equiv46,-54\equiv8,3\pmod{19}$.

Alternatively, we can complete the square:
\begin{align*}
  &\phantom{{}\iff{}}x^2+8x+5\equiv0\\
&\iff x^2+8x\equiv-5\\
&\iff x^2+8x+16\equiv11\\
%&\iff(x+4)^2\equiv11\\
&\iff(x+4)^2\equiv-8.
\end{align*}
From the table, $-8\equiv2^{12}$, so $\surd{-7}\equiv\pm2^6\equiv\pm7$,
and therefore $x\equiv-4\pm7\equiv3,-11\equiv3,8$.
\end{solution}
\end{compactenum}
\end{problem}


\end{document}