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

\usepackage[latin1]{inputenc}
\usepackage{bbm}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{stmaryrd}
\usepackage{xcolor}
\usepackage{pdflscape}
\usepackage{tikz-cd}
\usepackage{hyperref}

\usepackage{bussproofs}
\newcommand{\TagC}[1]{\RightLabel{\scriptsize #1}}

\theoremstyle{definition}
\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}
\newtheorem*{proposition}{Proposition}
\newtheorem*{definition}{Definition}
\newtheorem*{example}{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$}

\newcommand{\points}[1]{\hfill {\bf \color{darkgray} [#1 points]}}

\DeclareMathOperator{\circhat}{\widehat{\circ}}

\begin{document}
\thispagestyle{empty}
\begin{center}
{\Huge
15-151 Homework 8
}

Please submit in class at 8:00am on Tuesday 1st August
\end{center}

\subsection*{Exercises}

In the following exercises, the notation $[n]$, for $n \in \mathbb{N}$, refers to the set $\{ k \in \mathbb{N} \mid 1 \le k \le n \}$.

\begin{enumerate}[1.] \vspace{-10pt}
\item For each $a \in [14]$ coprime to $14$, find a multiplicative inverse for $a$ modulo $14$ and the order of $a$ modulo $14$.
\points{4}

\item The parts of this question form a proof of Fermat's little theorem. Throughout this question, $p$ is a prime modulus and $a$ is an integer not divisible by $p$.
\begin{enumerate}[(a)]
\item Explain why each element of $[p-1]$ is coprime to $p$.
\points{1}

\item Prove that, for each $x \in [p-1]$, there exists an element of $\{ a, 2a, \dots, (p-1)a \}$ which is congruent to $x$ modulo $p$.
\points{3}

\item Prove that, for all $k,\ell \in [p-1]$, if $ka \equiv \ell a \bmod p$, then $k=\ell$.
\points{3}

\item Use parts (b) and (c) to prove that $(p-1)! \equiv a^{p-1}(p-1)!$.
\points{3}

\textit{Hint: $a^{p-1}(p-1)! = a \times 2a \times \cdots \times (p-1)a$.}

\item Explain why this implies that $a^{p-1} \equiv 1 \bmod p$.
\points{2}
\end{enumerate}

\item Find the last two digits of $7^{7^{7^{7^{7^{7^{7}}}}}}$.
\points{6}

\textit{Hint: recall from class that $7^4 \equiv 1 \bmod 100$.}

\item For each of the following functions, determine (with proof) whether it is injective and whether it is surjective.
\begin{enumerate}[(a)]
\item $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ defined by $f(m,n) = 2^m(2n+1)$ for all $(m,n) \in \mathbb{N} \times \mathbb{N}$.
\points{5}

\item $q : \mathbb{Z} \times (\mathbb{Z} \setminus \{ 0 \}) \to \mathbb{Q}$ defined by $q(a,b) = \dfrac{a}{b}$ for all $(a,b) \in \mathbb{Z} \times (\mathbb{Z} \setminus \{ 0 \})$.
\points{5}
\end{enumerate}
\end{enumerate}

\subsection*{Project milestone}
Complete the questionnaire located at the following URL:

$ $ \hfill \url{https://goo.gl/forms/1CX86soJ3Kauki9A3}
\points{3}

\end{document}
