\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{hhline}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage[all,arc]{xy}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}
\input{preamble.tex}


\begin{document}

\homework{4: Cryptography (Modern) + Groups}{Due Tuesday, Week 5}



\textbf{Instructions}:  Do problems here until you have spent about 90 minutes working seriously on these questions.  Have fun!

\section*{Homework Problems}


\begin{enumerate}
\item If you haven't before: prove the binomial theorem!  I.e. show that for any positive integer $n$, and any $x, y$, we have
\begin{align*}
(x+y)^n=\sum_{i=0}^n{n \choose i}x^{n-i}y^i.
\end{align*}
\item Here's a second, very pretty proof of Fermat's Little Theorem.  Fill in the gaps!
\begin{theorem}
Let $p$ be a prime number.  Take any $a \neq 0$ in $\mathbb{Z}/p\mathbb{Z}$.  Then
\begin{align*}
a^{p-1} \equiv 1 \mod p.
\end{align*}
\end{theorem}
\begin{proof}
Suppose you have an alphabet with $a$ letters in it.  How many strings of length $p$ can you create?

The answer here is clearly $a^p$: we have $p$ places to put a letter, and $a$ choices for each letter; therefore, we have $\overbrace{a \cdot a \cdot \ldots \cdot a}^{p \textrm{ times}} = a^p$ many such strings.

Given any two strings, we say that they are \textbf{similar} if we can circularly shift the entries in one string to get the other string.  For example, the following four strings are all similar:
\begin{align*}
1121, 1112, 2111, 1211.
\end{align*}
Stack strings together into piles, where all of the strings in each pile are similar. Show that the following two statements are true:
\begin{itemize}
\item There are precisely $a$ strings that consist of the same symbol repeated $p$ times; these correspond to $a$ distinct piles each with one string in them.
\item  In every other pile, there are precisely $p$ strings.  In other words, if you're a string that's not just the same symbol repeated $p$ times, then there are exactly $p-1$ other strings that are similar to you.
\end{itemize}

Conclude from these two statements that $a^p \equiv a \mod p$, and therefore that $a^{p-1} \equiv 1 \mod p$.  

Explicitly perform this grouping operation for $a = 2, p=5$.  (If you're stuck on this proof, start here first!)
\end{proof}
\item A \textbf{group} is the following object: a set $G$ along with an operation $\cdot$ that satisfies the following four properties:
\begin{itemize}
\item \textbf{Associativity}: For all $a, b$ and $c$ in $G$, $(a \cdot b) \cdot c = a \cdot (b \cdot c).$
\item \textbf{Identity element}: There exists an element $e$ in $G$ such that for all $a$ in $G$, $e \cdot a = a \cdot e = a.$
\item \textbf{Inverse element}: For each $a$ in $G$, there is an element $b$ in $G$ such that $a \cdot b = b \cdot a = e$, where $e$ is an identity element.
\end{itemize}
\begin{enumerate}
\item Show that $\mathbb{Z}/n\mathbb{Z}$ is a group, if we let the group operation be defined as addition mod $n$.
\item Show that $\mathbb{Z}/n\mathbb{Z}$ is \textbf{not} a group, if we let the group operation be defined as multiplication mod $n$.
\item Let $\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$ denote the set of numbers $\{1, \ldots n-1\}$.  Show that this is a group precisely whenever $n$ is a prime number, if we let the group operation be defined as multiplication mod $n$.
\end{enumerate}
\item Let $G$ be a group with group operation $\cdot$ and identity element $e$.  For any $a$ in this group, let $a^k$ denote the object $\overbrace{a \cdot a \cdot \ldots \cdot a}^{k \textrm{ times}}$.  Let $n$ be the number of elements in this group.  Prove that 
\begin{align*}
a^{n} = e.
\end{align*}
\item \begin{enumerate}
\item Give me three groups that are not equal to $\langle\mathbb{Z}/n\mathbb{Z}, +\rangle$ or $\langle\left(\mathbb{Z}/n\mathbb{Z}\right)^\times, \cdot \rangle.$  For each, explain why they are groups.
\item Give me a group not in the above collection, containing only finitely many elements, that is not $\langle\mathbb{Z}/n\mathbb{Z}, +\rangle$ or $\langle\left(\mathbb{Z}/n\mathbb{Z}\right)^\times, \cdot \rangle.$ 
\end{enumerate}
\end{enumerate}
\end{document}