\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\color{red}\begin{quote}Solution:\quad 
\color{black} #1
\end{quote}\color{black}
}
\newcommand{\ba}{\backslash}
\DeclareMathOperator{\Gcd}{gcd}
\renewcommand{\gcd}[2]{\Gcd\left(#1, #2\right)}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\C}{\mathbb{C}}
\DeclareMathOperator{\Diam}{diam}
\newcommand{\Mod}[1]{\ (\bmod\ #1)}
\newcommand{\diam}[1]{\Diam\left(#1\right)}


\begin{document}
\title{Math 127 Homework}
\author{Mary Radcliffe}
\date{Due 8 March 2018}
\maketitle

Complete the following problems. Fully justify each response.

\begin{enumerate}

\item Let $a,b\in \Z$, $n\in \N$ with $n\geq 1$, and $k, \ell\in\N$ with $k\equiv \ell\Mod{n}$ and $a\equiv b\Mod{n}$.
\begin{enumerate}
\item Is it true that $a^k\equiv b^k\Mod{n}$? If so, prove it. If not, provide a counterexample.
\item Is it true that $a^k\equiv a^\ell\Mod{n}$? If so, prove it. if not, provide a counterexample.
\end{enumerate}

\item Let $a\in\Z$, and let $n\in\N$ with $n\geq 1$. Suppose that $a\perp n$. Show that $u, u'$ are both multiplicative inverses for $a$ if and only if $u$ is a multiplicative inverse for $a$ and $u\equiv u'\Mod{n}$.

\item Let $p$ be a positive prime, and $k\in \N$ with $k\geq 1$. Prove that $\varphi(p^k) = p^k-p^{k-1}$.

\item Read the proof of Theorem 3.3.49 and Example 3.3.51. Then prove that for any $b\in \N$ with $b\geq 2$, and $a\in \N$, $a$ is divisible by $b-1$ if and only if the sum of the base $b$ digits of $a$ is divisible by $b-1$.

\item For each of the following functions, determine if it is injective, surjective, both, or neither. Prove that your answers are correct.

\begin{enumerate}
\item $f:\Z\to\N$, $f(x) = x^2$.
\item $g:\N\to\Z$, $g(x)=x^2$.
\item $h:\R\to\Z$, $h(x) = \lfloor x\rfloor$ 

(note: $\lfloor x\rfloor$ is the number you get by rounding $x$ down to the nearest integer. Formally, we define \[\lfloor x\rfloor = \max\{ y\in \Z\ | \ y\leq x\}.\] You may be reasonably skeptical that such a number exists, since we cannot apply the Well-Ordering Principle here.... so if you are skeptical, prove it.)
\item $f: \N\to \Z$, $f(x) = \left\{\begin{array}{cl} \frac{x}{2} & x\hbox{ is even}\\ -\frac{x+1}{2} & x\hbox{ is odd}\end{array}\right.$
\end{enumerate}

\item Let $f:X\to Y$ and $g:Y\to Z$ be bijective functions. Prove that $g\circ f$ is also bijective. Is the converse true?
\end{enumerate}

\end{document}