\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm} %these packages let you use standard math symbols etc.
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{example}[theorem]{Example}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\title{Coding and Cryptography Fall 2016\\ Mission \#4 Template\\ Euler's Theorem}
\author{Katherine E. Stange}
\date{\today}
\begin{document}
\maketitle
{\bf Rules:} You {\bf may} use any written resources for help and information, but {\bf you may not copy}. Specifically, when you are writing, you {\bf must} have all resources (books, webpages) closed. Do not switch back and forth with any frequency. Instead, learn (not memorize) what you need to understand, and then {\bf write a complete proof in a vacuum, using only your brain}.
\newline
Instructions (erase these instructions): The goal is to fill out this document into a proper, respectable, chapter of a textbook describing Euler's Theorem. Replace each of the instructions with the appropriate, nicely written, definition, proof, example, etc.
\section{Euler's Phi Function}
\begin{definition}[Euler's Phi Function]
Provide a carefully written definition (in terms of counting invertible elements) of Euler's $\phi$ function here.
\end{definition}
\begin{example}
Here, give several small examples {\bf of your own creation}, from first principles. That means, count the invertible elements by actually listing them (and justifying the list; for example, give actual inverses).
\end{example}
\begin{proposition}
\label{prop:phip}
If $p$ is a prime, then $\phi(p) = p-1$.
\end{proposition}
This proposition requires lemmata.
\begin{lemma}
Let $n$ and $x$ be coprime integers. Then $x$ is invertible modulo $n$.
\end{lemma}
\begin{proof}
Provide a proof. You may use the Theorem at the top of page 68 of the text (refer to it B\'ezout's Lemma, also available on Wikipedia under this name). The proof is short when you base it on that theorem (in other words, it is a corollary of that theorem).
\end{proof}
\begin{lemma}
Suppose $x$ and $n$ are integers such that $x$ is invertible modulo $n$. Then $n$ and $x$ are coprime.
\end{lemma}
\begin{proof}
Provide a proof. Hint: invertibility allows one to write a linear combination of $n$ and $x$ that is $1$. Why does that imply coprimality?
\end{proof}
These two lemmata combine to give the following statement:
\begin{lemma}
Let $x$ and $n$ be integers. Then $x$ is invertible modulo $n$ if and only if $n$ and $x$ are coprime.
\end{lemma}
\begin{proof}[Proof of Proposition \ref{prop:phip}]
Provide a proof of Proposition \ref{prop:phip} here. Use the lemma just stated, and the definition of Euler's $\phi$.
\end{proof}
\begin{proposition}
\label{prop:phiprimepower}
Let $n = p^k$, where $p$ is a prime, $k\ge 1$. Then $\phi(n) = ???fill in the answer???$.
\end{proposition}
\begin{proof}
Provide a proof. You might like to count the non-coprime residues instead of the coprime ones.
\end{proof}
\begin{proposition}
\label{prop:phicrt}
Let $n$ and $m$ be coprime. Then $\phi(nm) = \phi(n)\phi(m)$.
\end{proposition}
This one needs a lemma again.
\begin{lemma}
Let $n$ and $m$ be coprime. Then $x$ is invertible modulo $nm$ if and only if it is invertible modulo $n$ and modulo $m$.
\end{lemma}
\begin{proof}
Provide a proof. One direction of the ``if and only if'' uses the Chinese Remainder Theorem, which you may call upon without proving. The other direction is immediate.
\end{proof}
\begin{proof}[Proof of Proposition \ref{prop:phicrt}]
Provide a proof of Proposition \ref{prop:phicrt} using the lemma.
\end{proof}
\begin{example}
Demonstrate how to compute $\phi(3 \cdot 7^2 \cdot 11^3)$ using the three propositions of this section. Cite each proposition as you use it.
\end{example}
\section{Euler's Theorem}
\begin{theorem}[Euler's Theorem]
\label{euler}
State Euler's Theorem here. It's on page 81 of your text, but as with everything else, learn what it is and then generate the statement without copying, please.
\end{theorem}
Before proving this, we will provide an example.
\begin{example}
Give an example demonstrating the theorem.
\end{example}
We need a lemma, which we proved in class, so you can use without proof. Here is its statement.
\begin{lemma}
Let $a$ be invertible modulo $n$. Then the function $f: \mathbb{Z}/n\mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}$ given by $f(x) = ax$ is bijective.
\end{lemma}
\begin{proof}[Proof of Theorem \ref{euler}]
Provide a proof of Euler's Theorem. Remember, the key idea is to form two lists and compare their products. You can remind yourself by looking at course notes or the proof of Fermat's Little Theorem on page 80 of your text. However, as I've emphasized before, you must internalize the argument, and then close all resources and write it, start to finish, without aids.
\end{proof}
\end{document}