\documentclass[%
version=last,%
a5paper,
10pt,%
headings=small,%
twoside,%
reqno,%
parskip=half,%
%draft=false,%
draft=true,%
DIV=classic,%
%DIV=12,%
%headinclude=true,%
%titlepage=true,%
pagesize]
{scrartcl}
%\usepackage{parskip}
\raggedright
\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}
\usepackage{amsmath,amsthm,amssymb,upgreek}

\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\divides}{\mid}
\newcommand{\ndivides}{\nmid}
\renewcommand{\theequation}{\fnsymbol{equation}}
\renewcommand{\leq}{\leqslant}

\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}
\title{MSGS\"U, MAT 221}
\subtitle{Final S\i nav\i\ \c c\"oz\"umleri}
\date{31 Aral\i k 2014, Saat 9:30}
\author{David Pierce}
\maketitle

Notland\i ran i\c cin \c c\"oz\"umlerinizin 
nas\i l okunaca\u g\i\ a\c c\i k olmal\i. 
%L\"utfen dikkat ederek yaz\i n.  
\.Ingilizceyi veya T\"urk\c ceyi kullanabilirsiniz.

\mbox{}

\begin{problem}
Let $p$ be prime and $0<k<p$.  We know $k!\cdot(p-k)!\divides p!$.
Show that
  \begin{equation*}
  p\left|\frac{p!}{k!\cdot(p-k)!}\right..
  \end{equation*}
\end{problem}

\begin{solution}
We are given that $p!=a\cdot k!\cdot(p-k)!$ for some $a$.
We want to show $p\divides a$.
We know $p\divides p!$, that is,
\begin{gather*}
  p\divides a\cdot k!\cdot(p-k)!.
\end{gather*}
But $p\ndivides k!$ and $p\ndivides (p-k)!$.
Therefore, by Euclid's Lemma, $p\divides a$.
\end{solution}


\begin{problem}
Assume $a$ is an odd integer.  For all natural numbers $k$, show
  \begin{equation*}
    a^{2^k}\equiv1\pmod{2^{k+2}}.
  \end{equation*}
\end{problem}

\begin{solution}
  We use induction.
  \begin{enumerate}
  \item 
When $k=1$, the claim is $a^2\equiv1\pmod8$ for all odd $a$.
This claim is true, since $(\pm1)^2\equiv1$ and $(\pm3)\equiv1\pmod8$.
\item
Suppose the claim is true when $k=\ell$.  
We want to show $2^{\ell+3}\divides a^{2^{\ell+1}}-1$.
We have
\begin{equation*}
  a^{2^{\ell+1}}-1
=\left(a^{2^{\ell}}\right)^2-1
=(a^{2^{\ell}}+1)(a^{2^{\ell}}-1).
\end{equation*}
By inductive hypothesis, $2^{\ell+2}\divides a^{2^{\ell}}-1$.
Since $a$ is odd, $2\divides a^{2^{\ell}}+1$. 
Therefore $2\cdot 2^{\ell+2}\divides a^{2^{\ell+1}}-1$.
  \end{enumerate}
\end{solution}



\begin{problem}
Find the least positive integer $x$ such that
\begin{align*}
  x&\equiv10\pmod{20}&&\And&x&\equiv3\pmod{23}.
\end{align*}
\end{problem}

\begin{solution}
  First apply the Euclidean algorithm to $20$ and $23$:
  \begin{align*}
&    \begin{aligned}
    23&=20+3,\\
20&=3\cdot6+2,\\
3&=2\cdot1+1,
     \end{aligned}&
&\begin{aligned}
  1&=3-2\\
&=3-(20-3\cdot6)=3\cdot7-20\\
&=(23-20)\cdot7-20=23\cdot7-20\cdot 8.
 \end{aligned}
  \end{align*}
Then
\begin{multline*}
  x\equiv10\cdot23\cdot7-3\cdot20\cdot8
=1610-480\\
=1130=460\cdot2+210\equiv210\pmod{460}.
\end{multline*}
Thus $x=210$.
\end{solution}



\begin{problem}
Find the least positive integer $x$ such that
\begin{equation*}
  7^{10\,000\,002}\equiv x\pmod{1375}.
\end{equation*}
\end{problem}

\begin{solution}
  $1375=5\cdot 275=5^2\cdot 55=5^3\cdot 11$, so
  \begin{equation*}
    \upphi(1375)=5^3\cdot11\cdot\frac45\cdot\frac{10}{11}=5^3\cdot 2^3=1000.    
  \end{equation*}
By Euler's Theorem,
$7^{1000}\equiv1\pmod{1375}$.
Since also
\begin{equation*}
10\,000\,002\equiv2\pmod{1000},
\end{equation*}
we have
$7^{10\,000\,002}\equiv 7^2\pmod{1375}$,
and thus $x=49$.
\end{solution}

\vfill
\end{document}