\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm} %these packages let you use standard math symbols etc.
\usepackage{enumitem}
\usepackage{geometry}
\setlist{nosep}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{conjecture}{Conjecture}
\newcommand{\ZZ}{\mathbb{Z}}
\title{\vspace{-5em}Coding and Cryptography Fall 2016\\ Proof Practice Worksheet - Solutions}
\author{Katherine E. Stange}
\date{\today}
\begin{document}
\maketitle %this is what makes the title from the data above
Practice makes perfect! Here are some basic items to practice proving, based on our course. Writing is half of what makes a proof a proof, so write well.
\begin{enumerate}
\item Prove that if $a_1 \equiv a_2 \pmod n$ and $b_1 \equiv b_2 \pmod n$, then $a_1 + b_1 \equiv a_2 + b_2 \pmod n$ (this is a fact we've been using all along).
\begin{theorem}
Suppose that $a_1, a_2, b_1, b_2, n \in \ZZ$, and that $a_1 \equiv a_2 \pmod n$ and $b_1 \equiv b_2 \pmod n$. Then $a_1 + b_1 \equiv a_2 + b_2 \pmod n$.
\end{theorem}
\begin{proof}
Suppose that $a_1, a_2, b_1, b_2, n \in \ZZ$, and that
\begin{align*}
a_1 &\equiv a_2 \pmod n, \\
b_1 &\equiv b_2 \pmod n.
\end{align*}
Then, by definition, $n \mid (a_1 - a_2)$ and $n \mid (b_1 - b_2)$. This implies that there are some integers $k$ and $\ell$ such that
\begin{align*}
a_1 - a_2 &= kn, \\
b_1 - b_2 &= \ell n.
\end{align*}
We wish to consider the difference
\begin{align*}
(a_1 + b_1) - (a_2 + b_2) &= (a_1 - a_2) + (b_1 - b_2) \\
&= kn + \ell n \\
&= (k + \ell)n.
\end{align*}
Since this difference is a multiple of $n$, we have shown that
\[
n \mid (a_1 + b_1) - (a_2 + b_2),
\]
or, in other words, that $a_1 + b_1 \equiv a_2 + b_2 \pmod n$.
\end{proof}
\newpage
\item Let $x$ be an element of $\ZZ/n\ZZ$. Suppose that $x$ has multiplicative order $k$. Prove that $k$ divides $\phi(n)$. (Hint: this is actually a more general group theory statement: if an element of a group has order $k$, then $k$ divides the order of the group.)
\begin{theorem}
Suppose that $x \in \ZZ/n\ZZ$ has multiplicative order $k$. Then $k \mid \phi(n)$.
\end{theorem}
\begin{proof}
Suppose that $x \in \ZZ/n\ZZ$ has multiplicative order $k$. Then, by this fact and by Euler's Theorem, we have two facts:
\begin{align*}
x^k &\equiv 1 \pmod n \\
x^{\phi(n)} &\equiv 1 \pmod n.
\end{align*}
This implies that
\[
x^{ak + b\phi(n)} \equiv 1^a1^b \equiv 1 \pmod n
\]
for any $a,b \in \ZZ$. In particular,
\[
x^{\gcd(k,\phi(n))} \equiv 1 \pmod n.
\]
But, by definition $k$ is the \emph{smallest} positive integer such that $x^k \equiv 1 \pmod n$, so that $k \le \gcd(k,\phi(n))$. But then (since $k \ge \gcd(k,\phi(n))$ by the definition of gcd), we conclude $k = \gcd(k,\phi(n))$. Therefore $k \mid \phi(n)$.
\end{proof}
\newpage
\item An element $x$ of $\ZZ/n\ZZ$ which is non-zero but satisfies $xy \equiv 0 \pmod n$ for some non-zero $y$ is called a \emph{zero divisor}. Prove that $\ZZ/n\ZZ$ has zero divisors if and only if $n$ is composite.
\begin{theorem}
The group $\ZZ/n\ZZ$ has zero divisors if and only if $n$ is composite.
\end{theorem}
\begin{proof}
Suppose that $\ZZ/n\ZZ$ has a zero divisor. Then there exists $x, y \in \ZZ/n\ZZ$, such that $x, y \not\equiv 0 \pmod n$, but such that $xy \equiv 0 \pmod n$. Then $n \mid xy$. If $n$ were prime, then this would imply $n \mid x$ or $n \mid y$, which is a contradiction. So $n$ is composite.
For the converse, suppose that $n$ is composite. Then we may write $n = ab$ for some $1 < a, b, < n$. In particular, $a, b \not\equiv 0 \pmod n$, but $ab \equiv 0 \pmod n$, i.e. we have located zero divisors in $\ZZ/n\ZZ$.
\end{proof}
\newpage
\item Suppose $\ZZ/n\ZZ$ has a primitive root. A primitive root is an element which has multiplicative order $\phi(n)$ modulo $n$. Show that the function $x \mapsto x^a$ on the invertible elements of $\ZZ/n\ZZ$ is bijective if and only if $\gcd(a,\phi(n))=1$.
\begin{theorem}
Suppose $\ZZ/n\ZZ$ has a primitive root. Consider the function
\[
f_a: (\ZZ/ n\ZZ)^* \rightarrow (\ZZ/n\ZZ)^*, \quad x \mapsto x^a.
\]
Then $f_a$ is bijective if and only if $\gcd(a,\phi(n))=1$.
\end{theorem}
\begin{proof}
First, suppose that $\gcd(a,\phi(n))=1$. Then $a$ is invertible modulo $\phi(n)$. In particular, for invertible $x$, we can compute, using the fact that $x^{\phi(n)} \equiv 1 \pmod n$, that
\begin{align*}
f_a \circ f_{a^{-1}}(x) &\equiv x^{a^{-1}a} \equiv x \pmod n, \\
f_{a^{-1}} \circ f_{a}(x) &\equiv x^{aa^{-1}} \equiv x \pmod n.
\end{align*}
Therefore, $f_a$ is invertible.
For the converse, suppose that $f_a$ is bijective, and let $g = \gcd(a, \phi(n))$. Then let $d = \phi(n)/g$. Then, $\phi(n) = dg$, so that
\[
(x^d)^a \equiv 1 \pmod n
\]
for any invertible $x$. But by bijectivity of $f_a$, this implies
\[
x^d \equiv 1 \pmod n
\]
for any invertible $x$. Since $d < \phi(n)$, this contradicts the existence of a primitive root.
\end{proof}
\end{enumerate}
\end{document}