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

\title{Number-theory exercises, VII}
\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}
    $f(568)=f(638)$ when $f\in\{\tau,\sigma,\phi\}$.
  \end{ex}

  \begin{ex}
    Solve:
    \begin{enumerate}
      \item
$n=2\phi(n)$.
\item
$\phi(n)=\phi(2n)$.
\item
$\phi(n)=12$.  (Do this without a table.  There are 6 solutions.)
    \end{enumerate}
  \end{ex}

  \begin{ex}
    Find a sequence $(a_n\colon n\in\N)$ of positive integers such that
    \begin{equation*}
      \lim_{n\to\infty}\frac{\phi(a_n)}{a_n}=0.
    \end{equation*}
(If you assume that there \emph{is} an answer to this problem, then it
    is not hard to see what the answer must be.  To actually
    \emph{prove} that the answer is correct, recall that, formally,
    \begin{equation*}
      \sum_n\frac 1n=\prod_p\frac1{1-\frac1p},
    \end{equation*}
so $\displaystyle\lim_{n\to\infty}\prod_{k=0}^n\frac1{1-\frac1{p_k}}=\infty$ if
$(p_k\colon k\in\N)$ is the list of primes.)
  \end{ex}

  \begin{ex}
    \begin{enumerate}
      \item
Show $a^{100}\equiv1\pmod{1000}$ if $\gcd(a,1000)=1$.
\item
Find $n$ such that $n^{101}\not\equiv n\pmod{1000}$.
    \end{enumerate}
  \end{ex}

  \begin{ex}
    \begin{enumerate}
      \item
Show $a^{24}\equiv1\pmod{35}$ if $\gcd(a,35)=1$.
\item
Show $a^{13}\equiv a\pmod{35}$ for all $a$.
\item
Is there $n$ such that $n^{25}\not\equiv n\pmod{35}$?
    \end{enumerate}
  \end{ex}

  \begin{ex}
    If $\gcd(m,n)=1$, show $m^{\phi(n)}\equiv n^{\phi(m)}\pmod{mn}$. 
  \end{ex}

  \begin{ex}
    If $n$ is odd, and is not a prime power, and if $\gcd(a,n)=1$,
    show $a^{\phi(n)/2}\equiv 1\pmod n$.
  \end{ex}

  \begin{ex}
    Solve $5^{10000}x\equiv1\pmod{153}$.
  \end{ex}

  \begin{ex}
    Prove $\displaystyle\sum_{d\divides
    n}\mu(d)\phi(d)=\prod_{p\divides n}(2-p)$.
  \end{ex}

  \begin{ex}
    If $n$ is \textbf{squarefree} (has no factor $p^2$), and $k\in\N$,
    show
    \begin{equation*}
      \sum_{d\divides n}\sigma(d^k)\phi(d)=n^{k+1}.
    \end{equation*}
  \end{ex}

  \begin{ex}
    $\displaystyle\sum_{d\divides n}\sigma(d)\phi\Bigl(\frac
    nd\Bigr)=n\tau(n)$. 
  \end{ex}

  \begin{ex}
    $\displaystyle\sum_{d\divides n}\tau(d)\phi\Bigl(\frac
    nd\Bigr)=\sigma(n)$. 
  \end{ex}
%\bibliographystyle{plain}
%\bibliography{../../../TeX/references}

%\layout


\end{document}