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

\title{Number-theory exercises, V}
\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{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}

As usual, $p$ and $q$ are primes.

  \begin{ex}
    The number $32\dsp 970\dsp 563$ is the product of two primes.  Find them.
  \end{ex}

  \begin{ex}
    Factorize $1\dsp 003\dsp 207$ (the product of two primes) knowing
    \begin{equation*}
      1\dsp 835^2\equiv598^2\pmod{1\dsp 003\dsp 207}.
    \end{equation*}
  \end{ex}

  \begin{ex}
    Compute $16{200}$ \emph{modulo} $19$.
  \end{ex}

  \begin{ex}
    If $p\neq q$, and $\gcd(a,pq)=1$, and
    $n=\lcm(p-1,q-1)$, show
    \begin{equation*}
    a^n\equiv1\pmod{pq}.
    \end{equation*}
  \end{ex}

  \begin{ex}
    Show $a^{13}\equiv a\pmod{70}$.
  \end{ex}

  \begin{ex}
    Assuming $\gcd(n,p)=1$, and $0\leq n<p$, solve the congruence
    \begin{equation*}
    a^nx\equiv b\pmod p.
    \end{equation*}
  \end{ex}

  \begin{ex}
    Solve $2^{14}x\equiv 3\pmod{23}$.
  \end{ex}

  \begin{ex}
    Show $\displaystyle\sum_{k=1}^{p-1}k^p\equiv0\pmod p$.
  \end{ex}

  \begin{ex}
    We can write the congruence $2^p\equiv2\pmod p$ as
    \begin{equation*}
      2^p-1\equiv 1\pmod p.
    \end{equation*}
Show that, if $n\divides 2^p-1$, then $n\equiv 1\pmod p$.
(\emph{Suggestion:}  Do this first if $n$ is a prime $q$.  Then
$2^{q-1}\equiv1\pmod q$.  If $q\not\equiv1\pmod p$, then $\gcd(p,q-1)=1$,
so $pa+(q-1)b=1$ for some $a$ and $b$.  Now look at
$2^{pa}\cdot2^{(q-1)b}$ \emph{modulo} $n$.)
  \end{ex}

  \begin{ex}
    Let $F_n=2^{2^n}+1$.  (Then $F_0,\dots,F_4$ are primes.)  Show 
    \begin{equation*}
      2^{F_n}\equiv2\pmod{F_n}.
    \end{equation*}
  \end{ex}



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

%\layout


\end{document}