\documentclass{article}
\usepackage{amssymb, mathrsfs, enumitem}
\usepackage{tikz-cd}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig, colortbl}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\theoremstyle{definition}
\newtheorem{prop}{Proposition}
\newtheorem{fact}{Fact}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\renewcommand{\today}{}


\addtolength{\topmargin}{-.875in}
\addtolength{\oddsidemargin}{-.8in}
\addtolength{\textwidth}{1.6in}
\addtolength{\textheight}{1.75in}


\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\la}{\Leftarrow}
\newcommand{\ra}{\Rightarrow}
\renewcommand{\iff}{\Leftrightarrow}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}
\DeclareMathOperator{\MOD}{mod}
\renewcommand{\mod}[1]{\ (\MOD\ #1)}
\DeclareMathOperator{\lcm}{lcm}
\renewcommand{\phi}{\varphi}

\newcommand{\inv}[1]{#1^{-1}}

\newcommand{\eps}{\epsilon}
\newcommand{\N}{\mathbb{N}}

\newcommand{\ba}{\backslash}


\begin{document}
\title{Math 127 Homework}
\author{Mary Radcliffe}
\date{Due 2 May 2019}
\maketitle

Complete the following problems. Fully justify each response. You need only turn in those problems marked with a (*).
\begin{enumerate}

\item (*) Use Euler's Totient Theorem to calculate $2^{105723}\mod{13}$.

\item Let $n\in\N$ and let $a\in \Z$ with $a\perp n$. Euler's Totient Theorem tells us that $a^{\phi(n)}\equiv 1\mod n$. Is it true that the order of $a$ must be $\phi(n)$? If so, prove it. If not, explain why not.

\item (*) Let $a, b\in \N$, with $a\perp b$. Prove that $\phi(ab)=\phi(a)\phi(b)$.


(Hint: Define $S_{ab}=\{m\in\N\ |\ m<ab, m\perp ab\}$, $S_a=\{m\in\N\ |\ m<ab, m\perp a\}$, and $S_b=\{m\in\N\ |\ m<ab, m\perp b\}$. Define a function $f:S_{ab}\to S_a\times S_b$ by $f(x)=(x\mod a, x\mod b)$. Show that this is well-defined and bijective.)

\item (*) Let $m, n$ be positive integers with $m \perp n$. Let $x, y$ be integers, such that $x \equiv y\mod n$ and $x \equiv y \mod m$. Prove that $x \equiv y \mod{ mn}$.

\item (*) If possible, solve the following system of congruences. If not possible, explain why not:
\[\begin{array}{l}x \equiv 4\mod{11}\\x\equiv 3\mod{17}\\x\equiv 6\mod{18}\end{array}\]

\item If possible, solve the following system of congruences. If not possible, explain why not:
\[\begin{array}{l}20x \equiv 9\mod{30}\\9x\equiv 12\mod{33}\\36x\equiv 48\mod{60}\end{array}\]

\item (*) A troop of 17 monkeys store their bananas in 11 piles of equal size, each
containing more than one banana, with a twelfth pile of 6 left over. When
they divide the bananas into 17 equal piles, none are left over. What is the
smallest number of bananas they can have?

\item Let $n\in\N$. For each $1\leq i\leq n$, let $a_i, b_i\in\R$ be real numbers with $a_i<b_i$, and let $I_i=[a_i, b_i]$, the corresponding real interval.

Define a relation $\leq$ on $\{I_1, I_2, \dots, I_n\}$ by $I_i\leq I_j$ iff $b_i\leq a_j$ or $i=j$. Prove that this is a partial order.

\item (CHALLENGE: BONUS 10 points) Let $n\in\N$ have prime decomposition $n=p_1^{k_1}p_2^{k_2}\dots p_r^{k_r}$. Use inclusion-exclusion to write $\phi(n)$ in terms of the primes $p_1, p_2, \dots, p_r$.



\end{enumerate}
\end{document}