\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm,amsfonts,verbatim}
\usepackage{microtype}
\usepackage{enumerate}
\usepackage{url}

\addtolength{\evensidemargin}{-.6in}
\addtolength{\oddsidemargin}{-.6in}
\addtolength{\textwidth}{1.0in}
\addtolength{\textheight}{1.9in}
\addtolength{\topmargin}{-.7in}

\theoremstyle{plain}
\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{challenge}[theorem]{Challenge Problem}
\newtheorem*{theoremqr}{Theorem~\ref{thmqr}}

\title{\vspace{-50pt}Elementary Number Theory\\
\normalsize Math 175, Section 30, Autumn 2010\\
\large Shmuel Weinberger ({\tt shmuel@math.uchicago.edu})\\
Tom Church ({\tt tchurch@math.uchicago.edu})\\
\url{www.math.uchicago.edu/~tchurch/teaching/175/}}
\author{}
\date{}

\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}

% \DeclareMathOperator{\sin}{sin}   %% just an example (it's already defined)
\DeclareMathOperator{\norm}{norm}


\renewcommand{\baselinestretch}{1.2}
\begin{document}
\maketitle
\setcounter{section}{5}
\vspace{15pt}
\begin{center}
{\huge \bf Script 5: Primitive Roots}
\end{center}

\vspace{40pt}

\renewcommand{\baselinestretch}{1.2}

\begin{definition}
Let $k$ be a positive integer, and let $R$ be a field. Given $x\in R$, we say that $x$ is a \emph{$k$-th root of unity} if $x^k=1$. We say that $x$ is a \emph{\textbf{primitive} $k$-th root of unity} if it is not an $\ell$-th root of unity for any smaller $\ell$: that is, $x^k=1$ and $x^\ell\neq 1$ for all $1\leq \ell<k$.
\end{definition}

\begin{theorem}
If $x^a=1$ and $x^b=1$, then $x^{\gcd(a,b)} = 1$.
\end{theorem}

\begin{theorem}If $x$ is a primitive $k$-th root of unity, and $x$ is an $m$-th root of \mbox{unity, then $k|m$}.
\end{theorem}

\begin{lemma}
If $x$ is a primitive $k$-th root of unity in $R$, then the number of $k$-th roots of unity in $R$ is at least $k$.
\end{lemma}

\begin{theorem}If there exists a primitive $k$-th root of unity in a field $R$, the number of $k$-th roots of unity in $R$ is exactly $k$.
\end{theorem}\vskip20pt

\begin{exercise}\ 
\begin{enumerate}[a)]\item Find a primitive cube root of unity in $\Z/7\Z$.
\item Find a primitive cube root of unity in $\Z/13\Z$.
\item Find a primitive cube root of unity in $\Z/19\Z$.
\end{enumerate}
\end{exercise}

\begin{theorem}
Let $p$ be a prime number. There exists a primitive cube root of unity in $\Z/p\Z$ if and only if $p\equiv 1\pmod{3}$.
\end{theorem}\pagebreak


\begin{definition}Let $q$ be a prime number and 
\[S=\left\{(a_1,\ldots,a_q)\Big|a_i\in R^\times,\ a_1a_2\cdots a_q=1\right\}\]
be the set of length-$q$ sequences of elements of $R^\times$ whose product is 1. If $(a_1,a_2,\ldots,a_q)\in S$ is such a sequence, we can ``rotate'' the sequence to obtain a new sequence $(a_2,\ldots,a_q,a_1)\in S$.\linebreak We say that a sequence is \emph{rotation-invariant} if rotation yields the same sequence: \[(a_1,a_2,\ldots,a_q)=(a_2,\ldots,a_q,a_1).\]
We always have the trivial example of a rotation-invariant sequence \mbox{in $S$, namely $(1,1,\ldots,1)\in S$.}
\end{definition}

\begin{lemma}
Let $q$ be a prime number. If $q$ divides the size of $R^\times$, then $S$ contains some nontrivial rotation-invariant sequence $(a_1,\ldots,a_q)$.
\end{lemma}

\begin{theorem}
Let $q$ be a prime number. There exists a primitive $q$-th root of unity in $\Z/p\Z$ if and only if $p\equiv 1\pmod{q}$.
\end{theorem}\vskip20pt

\begin{theorem}
Let $k$ and $\ell$ be relatively prime: $(k,\ell)=1$. If $x$ is a primitive $k$-th root of unity in $R$, and $y$ is a primitive $\ell$-th root of unity in $R$, then there exists a primitive $k\ell$-th root of unity in $R$.
\end{theorem}\vskip40pt



\begin{theorem}
Let $q$ be a prime number, and let $k$ be a positive integer. There exists a primitive $q^k$-th root of unity in $\Z/p\Z$ if and only if $p\equiv 1\pmod{q^k}$.\\[7pt]
\noindent Hint: prove by induction on $k$, and consider the set:
\[T=\left\{(a_1,\ldots,a_q)\Big|a_i\in \Z/p\Z^\times,\ a_1a_2\cdots a_q\text{ is a $q^{k-1}$-th root of unity}\right\}\]
\end{theorem}\vskip10pt

\begin{theorem}
Let $p$ be a prime number. There exists an element $a\in \Z/p\Z$ so that every nonzero element of $\Z/p\Z$ is a power of $a$.
\end{theorem}

\end{document}