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

\title{Number-theory exercises, VIII}
\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{ex}{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{ex}
    We have $(\pm3)^2\equiv2\pmod7$.  Compute the orders of $2$, $3$,
    and~$-3$, \emph{modulo} $7$.
  \end{ex}

  \begin{ex}
Suppose $\ord na=k$, and $b^2\equiv a\pmod n$.
\begin{enumerate}
  \item
Show that $\ord nb\in\{k,2k\}$.
\item
Find an example for each possibility of $\ord nb$.
\item
Find a condition on $k$ such that $\ord nb=2k$.
\end{enumerate}
  \end{ex}

  \begin{ex}
This is about $23$:
    \begin{enumerate}
      \item\label{part:a}
Find a primitive root of least absolute value.    
\item
How many primitive roots are there?
\item
Find these primitive roots as powers of the root found
in~\eqref{part:a}.
\item
Find these primitive roots as elements of $[-11,11]$.
    \end{enumerate}
  \end{ex}

  \begin{ex}
    Assuming $\ord pa=3$, show:
    \begin{enumerate}
      \item
$a^2+a+1\equiv0\pmod3$;
\item
$(a+1)^2\equiv a\pmod 3$;
\item
$\ord p{a+1}=6$.
    \end{enumerate}
  \end{ex}

  \begin{ex}
    Find all elements of $[-30,30]$ having order $4$
    \emph{modulo} $61$.
  \end{ex}

  \begin{ex}
$f(x)\equiv0\pmod n$ may have more than $\deg(f)$ solutions:
    \begin{enumerate}
      \item
Find four solutions to $x^2-1\equiv0\pmod{35}$.
\item
Find conditions on $a$ such that the congruence
$x^2-a^2\equiv0\pmod{35}$ has four distinct solutions, and find these
solutions.
\item
If $p$ and $q$ are odd primes, find conditions on $a$ such that the
congruence $x^2-a^2\equiv0\pmod{pq}$ has four distinct solutions, and
find these solutions.
    \end{enumerate}
  \end{ex}

  \begin{ex}
    If $\ord na=n-1$, then $n$ is prime.
  \end{ex}

  \begin{ex}
If $a>1$, show $n\divides\phi(a^n-1)$.
  \end{ex}

  \begin{ex}
If $2\ndivides p$ and $p\divides n^2+1$, show
    $p\equiv1\pmod4$. 
  \end{ex}

  \begin{ex}\mbox{}
    \begin{enumerate}
      \item
Find conditions on $p$ such that, if $r$ is a primitive root of $p$,
then so is $-r$.
\item
If $p$ does not meet these conditions, then what is $\ord p{-r}$?
    \end{enumerate}
  \end{ex}


%\bibliographystyle{plain}
%\bibliography{../../../TeX/references}

%\layout


\end{document}