\documentclass[%
version=last,%
a5paper,
10pt,%
headings=small,%
twoside,%
reqno,%
parskip=half,%
%draft=false,%
draft=true,%
%DIV=classic,%
DIV=10,%
%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{B\"ut\"unleme S\i nav\i}
\author{David Pierce}
\date{19 Ocak 2015, Saat 13:30}
\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. 
\.Ingilizceyi veya T\"urk\c ceyi kullanabilirsiniz.


\begin{problem}
Find the least positive integer $x$ such that
\begin{equation*}
  3^{99995}\cdot x\equiv1\pmod{27500}.
\end{equation*}
\end{problem}

\begin{solution}
We have $27500=2^2\cdot5^2\cdot275=2^2\cdot5^3\cdot55=2^2\cdot5^4\cdot11$, so
\begin{equation*}
    \upphi(27500)=2^2\cdot 5^4\cdot11\cdot\frac12\cdot\frac45\cdot\frac{10}{11}
=2^4\cdot 5^4=10000.  
\end{equation*}
Since $\gcd(3,27500)=1$, we have
$3^{10000}\equiv1\pmod{27500}$,
by Euler's Theorem; also, \emph{modulo} $27500$,
\begin{comment}
  

\begin{equation*}
  3^{99995}\cdot x\equiv 1
\iff3^{100000}\cdot x\equiv 3^5
\iff(3^{10000})^{10}\cdot x\equiv3^5
\iff x\equiv3^5.
\end{equation*}


\end{comment}
\begin{align*}
&\phantom{{}\iff{}}3^{99995}\cdot x\equiv 1\\
&\iff3^{100000}\cdot x\equiv 3^5\\
&\iff(3^{10000})^{10}\cdot x\equiv3^5\\
&\iff x\equiv3^5.
\end{align*}
Thus $x=3^5=243$ 
(this is the least positive integer that is congruent to 
$3^5$ \emph{modulo} $27500$).
\end{solution}


\begin{problem}
Show that, for all primes $p$ and all natural numbers $k$ and $\ell$,
\begin{equation*}
\upsigma(p^{k+\ell})\leq\upsigma(p^k)\cdot\upsigma(p^{\ell}).
\end{equation*}
(Since $\sigma$ is multiplicative, this shows that,
for arbitrary natural numbers $a$ and $b$,
$\upsigma(ab)\leq\upsigma(a)\cdot\upsigma(b)$.)
\end{problem}

\begin{solution}
Since $\upsigma(p^k)=(p^{k+1}-1)/(p-1)$, it is enough to show
\begin{equation*}
  \frac{p^{k+\ell+1}-1}{p-1}\leq
  \frac{p^{k+1}-1}{p-1}\cdot
  \frac{p^{\ell+1}-1}{p-1},
\end{equation*}
or equivalently
\begin{gather*}
  (p^{k+\ell+1}-1)(p-1)\leq(p^{k+1}-1)(p^{\ell+1}-1),\\
p^{k+\ell+2}-p^{k+\ell+1}-p+1\leq 
p^{k+\ell+2}-p^{\ell+1}-p^{k+1}+1,\\
p^{\ell+1}-p\leq p^{k+\ell+1}-p^{k+1},\\
1\leq p^k.
\end{gather*}
Since indeed $1\leq p^k$, 
we must have $\upsigma(p^{k+\ell})\leq\upsigma(p^k)\cdot\upsigma(p^{\ell}).
$.
\end{solution}


\begin{problem}
Suppose $p$ is prime, 
and $r$ is such that, for some $m$ such that $p\ndivides m$,
\begin{equation*}
  r^{p-1}=1+m\cdot p.
\end{equation*}
Show that, for every natural number $k$, 
for some $m$ such that $p\ndivides m$,
\begin{equation*}
  r^{p^{k-1}\cdot(p-1)}=1+m\cdot p^k.
\end{equation*}
You may use that $p\divides\binom pj$ whenever $0<j<p$.
\end{problem}

\begin{solution}
  We use induction.
We are given that the claim is true when $k=1$.
Suppose it is true when $k=\ell$, so that, 
for some $n$ such that $p\ndivides n$,
\begin{equation*}
  r^{p^{\ell-1}\cdot(p-1)}=1+n\cdot p^{\ell}.  
\end{equation*}
Then
\begin{align*}
  r^{p^{\ell}\cdot(p-1)}
&=(1+n\cdot p^{\ell})^p\\
&=1+n\cdot p\cdot p^{\ell}
+n^2\cdot\binom p2\cdot p^{2\ell}
%+n^3\cdot\binom p3\cdot p^{3\ell}
+\dots+n^p\cdot p^{p\ell}\\
&=1+\left(n+\underbrace{n^2\cdot\binom p2\cdot p^{\ell-1}+\dots
+p^{(p-1)\cdot\ell-1}}_s\right)\cdot p^{\ell+1}\\
&=1+(n+s)\cdot p^{\ell+1},
\end{align*}
where $p\divides s$, so $p\ndivides n+s$.
Thus the claim is true when $k=\ell+1$, assuming it is true when $k=\ell$.
By induction, the claim is true for all $k$.
\end{solution}



\begin{problem}
Find the least positive integer $x$ such that
\begin{align*}
  x&\equiv2\pmod{34}&&\And&x&\equiv1\pmod{21}.
\end{align*}
\end{problem}

\begin{solution}
  First apply the Euclidean algorithm to $34$ and $21$:
  \begin{align*}
&    \begin{aligned}
34&=21+13,\\
21&=13+8,\\
13&=8+5,\\
8&=5+3,\\
5&=3+2,\\
3&=2+1,
     \end{aligned}&
&\begin{aligned}
1
&=3-2\\
&=3-(5-3)=3\cdot2-5\\
&=(8-5)\cdot2-5=8\cdot2-5\cdot 3\\
&=8\cdot2-(13-8)\cdot3=8\cdot5-13\cdot3\\
&=(21-13)\cdot5-13\cdot3=21\cdot5-13\cdot8\\
&=21\cdot5-(34-21)\cdot8=21\cdot13-34\cdot8.
 \end{aligned}
  \end{align*}
Then
\begin{align*}
  x
&\equiv2\cdot21\cdot13-34\cdot8\\
&\equiv21\cdot13+21\cdot13-34\cdot8\\
&\equiv21\cdot13+1\pmod{34\cdot21},
\end{align*}
and therefore $x=21\cdot13+1=274$.
This is easily checked: 
immediately $21\cdot13+1\equiv1\pmod{21}$;
also $34\cdot8=272$, so $274\equiv2\pmod{34}$.
\end{solution}

\vfill
\end{document}