%\documentclass[a4paper,twoside,draft]{article}
\documentclass[a4paper,twoside,draft,12pt]{amsart}

\title{Number-theory exercises, X}
\author{David Pierce}
\date{\today}

\address{Mathematics Dept\\
Middle East Tech.\ Univ.\\
Ankara 06531, Turkey}

\email{dpierce@metu.edu.tr}
\urladdr{http://www.math.metu.edu.tr/~dpierce/}


\usepackage{amssymb,amsmath,amsthm}
%\usepackage{amscd}     % commutative diagram
%\usepackage[mathscr]{euscript}
\usepackage{url}
\usepackage{verbatim}  % allows a comment environment:

%\usepackage{parskip}   % paragraphs not indented, but separated by spaces

\usepackage{eco}  % gives old-style numerals

\input{../Notes/abbrevs}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Theorem-like environments  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\swapnumbers


%\newtheorem{theorem}{Theorem}
%\newtheorem{axdef}[theorem]{Axiom and definition}
%\newtheorem{lemma}[theorem]{Lemma}

\theoremstyle{definition}

%\newtheorem{definition}[theorem]{Definition}
%\newtheorem{parag}[theorem]{}
%\newtheorem{ex}[theorem]{Exercise}
\newtheorem{xca}{Exercise}

\theoremstyle{remark}

%\newtheorem{remarks}[theorem]{Remarks}
%\newtheorem{remark}[theorem]{Remark}

%\newcommand{\rmk}[1]{\marginpar[\flushright#1]{\flushleft#1}}

\begin{document}
  \maketitle\thispagestyle{empty}

  \begin{xca}
The Law of Quadratic Reciprocity makes it easy to compute many Legendre
symbols, but this law is not always needed.  Compute $(n/17)$ and
$(m/19)$ for as many $n$ in $\{1,2,\dots,16\}$ and $m$ in
$\{1,2,\dots,18\}$ as you can, 
using only that, whenever $p$ is an odd prime, and $a$ and $b$ are
prime to $p$, then:
\begin{itemize}
  \item
$a\equiv b\pmod p\implies(a/p)=(b/p)$;
\item
$(1/p)=1$;
\item
$(-1/p)=(-1)^{(p-1)/2}$\;;
\item
$(a^2/p)=1$;
\item
$(2/p)=
  \begin{cases}
    1,&\text{ if }p\equiv\pm1\pmod8;\\
   -1,&\text{ if }p\equiv\pm3\pmod8.
  \end{cases}$
\end{itemize}
  \end{xca}

\vfill
  \begin{xca}
    Compute all of the Legendre symbols $(n/17)$ and $(m/19)$ by means
    of Gauss's Lemma. 
  \end{xca}
\vfill
  \begin{xca}
    Find all primes of the form $5\cdot 2^n+1$ that have $2$ as a
    primitive root.
  \end{xca}
\vfill
  \begin{xca}
    For every prime $p$, show that there is an integer $n$ such that
    \begin{equation*}
      p\divides(3-n^2)(7-n^2)(21-n^2).
    \end{equation*}
  \end{xca}
\vfill
  \begin{xca}\mbox{}
    \begin{enumerate}
      \item
If $a^n-1$ is prime, show that $a=2$ and $n$ is prime.
\item
Primes of the form $2^p-1$ are called \textbf{Mersenne primes.}
Examples are $3$, $7$, and $31$.
Show
that, if $p\equiv3\pmod4$, and $2p+1$ is a prime $q$, then
$q\divides2^p-1$, and therefore $2^p-1$ is not prime.  (\emph{Hint:}
Compute $(2/q)$.)
    \end{enumerate}
  \end{xca}

\vfill
  \begin{xca}
    Assuming $p$ is an odd prime, and $2p+1$ is a prime $q$, show that $-4$
    is a primitive root of $q$.  (\emph{Hint:}  Show $\ord
    q{-4}\notin\{1,2,p\}$.) 
  \end{xca}
\vfill
%\bibliographystyle{plain}
%\bibliography{../../../TeX/references}

%\layout


\end{document}

