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

\title{Number-theory exercises, IX}
\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}
For $(\Z/(17))^{\times}$:
    \begin{enumerate}
\item
construct a table of logarithms using $5$ as the base; 
\item
using this (or some other table, with a different base), solve:
\begin{enumerate}
  \item
$x^{15}\equiv14\pmod{17}$;
\item
$x^{4095}\equiv14\pmod{17}$;
\item
$x^4\equiv4\pmod{17}$;
\item
$11x^4\equiv7\pmod{17}$.
\end{enumerate}
    \end{enumerate}
  \end{xca}

  \begin{xca}
    If $n$ has primitive roots $r$ and $s$, and
    $\gcd(a,n)=1$, prove
    \begin{equation*}
      \log_sa\equiv\frac{\log_ra}{\log_rs}\pmod{\phi(n)}.
    \end{equation*}
  \end{xca}

  \begin{xca}
    In $(\Z/(337))^{\times}$, for any base, show 
    \begin{equation*}
    \log(-a)\equiv\log a+168\pmod{336}.
    \end{equation*}
  \end{xca}

  \begin{xca}
    Solve $4^x\equiv13\pmod{17}$.
  \end{xca}

  \begin{xca}
How many primitive roots has $22$?  Find them.
  \end{xca}

  \begin{xca}
    Find a primitive root of $1250$.
  \end{xca}

  \begin{xca}
    Define the function $\lambda$ by the rules
    \begin{align*}
\lambda(2^k)&=
\begin{cases}
  \phi(2^k),&\text{ if }0<k<3;\\
  \phi(2^k)/2,&\text{ if }k\geq3;
\end{cases}\\
%\lambda\Bigl(2^k\cdot\prod_{p\in A}p^{\ell(p)}\Bigr)
%&=\lcm(\{\lambda(2^k)\}\cup\{\phi(p^{\ell(p)})\colon p\in A\}),
\lambda(2^k\cdot p_1{}^{\ell(1)}\dotsm p_m{}^{\ell(m)})
&=\lcm(\phi(2^k),\phi(p_1{}^{\ell(1)}),\dotsc,\phi(p_m{}^{\ell(m)})).
    \end{align*}
where the $p_i$ are distinct odd primes.
\begin{enumerate}
  \item
Prove that, if $\gcd(a,n)=1$, then $a^{\lambda(n)}\equiv1\pmod n$.
\item
Using this, show that, if $n$ is not $2$ or $4$ or an odd prime power
or twice an odd prime power, then $n$ has no primitive root.
\end{enumerate}
  \end{xca}

  \begin{xca}
    Solve the following quadratic congruences.
    \begin{enumerate}
      \item
$8x^2+3x+12\equiv0\pmod{17}$;
\item
$14x^2+x-7\equiv0\pmod{29}$;
\item
$x^2-x-17\equiv0\pmod{23}$;
\item
$x^2-x+17\equiv0\pmod{23}$.
    \end{enumerate}
  \end{xca}

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

%\layout


\end{document}