\newpage\documentclass[11pt,onecolumn,fleqn]{article}

\usepackage[latin1]{inputenc}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{xcolor}

\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\setlength{\oddsidemargin}{0px}
\setlength{\textwidth}{460px}
\setlength{\voffset}{-1.5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0px}
\setlength{\parskip}{10pt}

\newcommand{\TT}{$\checkmark$}
\newcommand{\FF}{$\times$}


\begin{document}
\thispagestyle{empty}
\begin{center}
{\Huge 21-128 and 15-151 problem sheet 5}

Solutions to the following seven exercises and optional bonus problem are to be submitted through 
blackboard by 8:30AM on

\textbf{Thursday 13th October 2016.}

There are also some practice problems, not to be turned in, for those seeking more practice
and also for review prior to the exam.

\end{center}


\subsubsection*{Problem 1} Let $p$ be a prime number greater than 2. Prove that $\frac{2}{p}$
can be expressed in exactly one way in the form $\frac1m + \frac1n$ where $m$ and $n$ are postive
integers with $n > m$.


\subsubsection*{Problem 2}
For $x,y,z \in \mathbb{Z}$, suppose that $5$ divides $x^2+y^2+z^2$. Prove that $5$ divides at least one of $x$, $y$ or $z$.


\subsubsection*{Problem 3}
Let $m$ and $n$ be positive, relatively prime integers, and $r$ and $s$ be integers such that $mr \equiv 1 \bmod n$ and $ns \equiv 1 \bmod m$. For fixed integers $a,b$, find an integer value of $x$ in terms of $a,b,m,n,r,s$ satisfying $x \equiv a \bmod n$ and $x \equiv b \bmod m$.


\subsubsection*{Problem 4}
Let $m$ and $n$ be positive, relatively prime integers, and $x$ and $y$ be integers such that
$x \equiv a \bmod n$ and $x \equiv b \bmod m$, and also 
$y \equiv a \bmod n$ and $y \equiv b \bmod m$ (here $a$ and $b$ are fixed, unknown integers).
Show that $x \equiv y \bmod mn$.


\subsubsection*{Problem 5}
The base $10$ representation of an integer is \textit{palindromic} if the digits read the same when written forward or backward. 
Prove that every palindromic integer with an even number of digits is divisible by $11$. 


\subsubsection*{Problem 6} Show your work in the following computations.

(i) Determine the unknown digits $a$ and $b$ in 3a27b given that $3a27b \equiv 1 \bmod 9$ 
\newline and $3a27b \equiv 9 \bmod 11$.

(ii) Let $p$ be a positive prime number. Determine the remainder left
when \newline $1^{p-1} \times 2^{p-1} \times \dots \times (p-1)^{p-1}$ is divided by $p$.

(iii) Use congruence mod $9$ to find the missing digit ? in $92854 \cdot 16284 = 151?034536$.

(iv) Find the remainder when $3^{100}$ is divided by $7$.

(v) Find the remainder when $3^{100}$ is divided by $15$.


\subsubsection*{Problem 7}
Let $p$ be a prime larger than 2. Prove that $2(p-3)! \equiv -1 \bmod p$. [\textit{Hint: use Wilson's theorem.}]


\subsubsection*{Bonus Problem - 2 points}
Let $p$ be a positive prime which leaves a remainder of 1 upon division by 4. Show that $p$ divides $((\frac{p-1}{2})!)^2 + 1$.


\subsubsection*{Extra Problem 1}
$1500$ soldiers arrive in training camp. A few soldiers desert the camp. The drill sergeants divide the remaining soldiers 
into groups of five and discover there is one left over. When they divide them into groups of seven, there are three left over. 
When they divide them into groups of eleven, there are again three left over. Determine the number of deserters.


\subsubsection*{Extra Problem 2}
Let $k$ be an odd integer. Show that $k^2 - 1$ is divisible by 8.


\subsubsection*{Extra Problem 3}
Let $p$ be a positive prime and $k$ be an integer. Prove that $k^2 \equiv 1 \bmod p$ implies ($k \equiv 1 \bmod p$ or
$k \equiv -1 \bmod p$).

\end{document}
