\documentclass{article}

\def\ifsoln{\iftrue}

\usepackage{amsthm}
\usepackage{array}
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{comment}
\usepackage{graphicx}
\usepackage[colorlinks=true]{hyperref}
\usepackage{setdeck}
\usepackage{tikz}
\usepackage{booktabs}
%\usepackage[notref,notcite]{showkeys}

\theoremstyle{definition}
\newtheorem{question}{Question}
\newtheorem{definition}[question]{Definition}
\newtheorem{hw}[question]{Homework}

\theoremstyle{remark}
\newtheorem{remark}[question]{Remark}

\theoremstyle{plain}
\newtheorem{theorem}[question]{Theorem}

\ifsoln
\newenvironment{answer}{\begin{proof}[Answer]}{\end{proof}}
\else
\excludecomment{answer}
\fi

\ifweb
\newenvironment{webonly}{}{}
\else
\excludecomment{webonly}
\fi

\def\lcm{\operatorname{lcm}}

\begin{document}

\title{Math 3110:  Number Theory}
\author{Exploration 3:  Quadratic equations}
\date{\today}
\maketitle

\section{Quadratic residues}

Suppose that $p$ is a nonzero prime integer.  We saw in the last exploration that $-1$ is a square in $\mathbb F_p$ if and only if $p$ fails to be prime in $\mathbb Z[i]$.  But how can we tell if $-1$ is a square in $\mathbb F_p$?

\begin{definition}
An element $z$ of $\mathbb F_p$ is called a \emph{quadratic residue} modulo $p$ if there is some $x \in \mathbb F_p$ such that $x^2 = z$.  More generally, if $F$ is a finite field with $q$ elements, we will call $z \in F$ a \emph{quadratic residue} in $F$ if there is some $x \in F$ such that $x^2 = z$.
\end{definition}

\begin{theorem}[Fermat's little theorem]
If $F$ is a finite field of size $q$ and $a \in F^\ast$ then $a^{q-1} = 1$.
\end{theorem}

\begin{theorem}
If $F$ is a field and $p(x)$ is a polynomial of degree $d$ with coefficients in $F$ then $p$ has at most $d$ roots in $F$.
\end{theorem}

\begin{question}
Pick a few small fields and make a table of all of the quadratic residues and quadratic nonresidues in each one.  How many quadratic residues are there?  Can you conjecture a general pattern?
\end{question}

\begin{question}
Pick a field $F$ of size $q$ and an $x \in F$.  Compute $x^{\frac{q-1}{2}}$.  Do this for a few examples.  Compare  your answers to the results of the last question.  Can you observe a pattern?
\end{question}

\begin{theorem}
Let $F$ be a finite field with an odd number of elements.  Then an element $a \in F$ is a nonzero quadratic residue if and only if $a^{\frac{q-1}{2}} = 1$.
\end{theorem}

\begin{theorem}
Suppose that $p$ is an odd prime integer.  Then $-1$ is a quadratic residue in $\mathbb F_p$ if and only if $p \equiv 1 \pmod{4}$.
\end{theorem}

\section{Quadratic reciprocity}

Suppose that $p$, $q$, and $r$ are nonzero prime integers.  If $p \equiv q \pmod{r}$ then $p$ is a quadratic residue modulo $r$ if and only if $q$ is a quadratic residue modulo $r$.  But is there any relationship between whether $r$ is a quadratic residue modulo $p$ and whether $r$ is a quadratic residue modulo $q$.  We certainly don't have any reason yet to expect a relationship.  But let's compute some data and see if we can make any observations:

\begin{question}
Choose $a \in \mathbb F_5^\ast$.  Make a list of primes $p$ such that $p \equiv a \pmod{5}$.  For each $p$ in your list, determine whether $5$ is a quadratic residue modulo $p$.  Do you observe any patterns?
\end{question}

\begin{question}
Choose $a \in \mathbb F_3^\ast$.  Make a list of primes $p$ such that $p \equiv a \pmod{3}$.  For each $p$ in your list, determine whether $3$ is a quadratic residue modulo $p$.  Do you observe any patterns?
\end{question}

\begin{question}
Repeat your experiments with $3$ and $5$ replaced by other small prime integers.
\end{question}

\end{document}
