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

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

\address{Mathematics Dept\\
Middle East Technical University\\
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

These exercises are for Elementary Number Theory I (Math 365
at METU).  In them, if a \emph{statement} is given that is not a
definition, then 
the exercise is to prove the statement.

A first set of exercises is the proofs not given in~\cite{DPfnth}.
The exercises below are mostly inspired by exercises in \cite[Ch.~2]{Burton}.

Recall that the \defn{triangular numbers}{} compose a sequence
$(t_n\colon n\in\N)$, defined recursively by $t_0=0$ and
$t_{n+1}=t_n+n+1$. 

\begin{ex}
  An integer $n$ is a triangular number if and only if
  $8n+1$ is a square number.
\end{ex}

\begin{ex}\mbox{}
  \begin{enumerate}
    \item
If $n$ is triangular, then so is $9n+1$.
\item
Find infinitely many pairs $(k,\ell)$ such that, if $n$ is triangular,
then so is $kn+\ell$.
  \end{enumerate}
\end{ex}

\begin{ex}
  If $a=n(n+3)/2$, then $t_a+t_{n+1}=t_{a+1}$.
\end{ex}

\begin{ex}
  The \defn{pentagonal numbers}{} are $1$, $5$, $12$, \dots: call these $p_1$,
  $p_2$, \&c.
  \begin{enumerate}
    \item
Give a recursive definition of these numbers.
\item
Find a closed expression for $p_n$ (that is, an expression not
involving $p_{n-1}$, $p_{n-2}$, \&c.). 
\item
Find such an expression involving triangular numbers and square numbers.
  \end{enumerate}
\end{ex}

\begin{ex}\mbox{}
  \begin{enumerate}
    \item
$7\divides2^{3n}+6$.
\item
Given $a$ in $\Z$ and $k$ in $\N$, find integers $b$ and $c$ such
that $b\divides a^{kn}+c$ for all $n$ in $\N$.
  \end{enumerate}
\end{ex}

\begin{ex}
$\gcd(a,a+1)=1$.
\end{ex}

\begin{ex}
$(k!)^n\divides(kn)!$ for all $k$ and $n$ in $\N$.
\end{ex}

\begin{ex}
If $a$ and $b$ are co-prime, and $a$ and $c$ are
  co-prime, then $a$ and $bc$ are co-prime.
\end{ex}

\begin{ex}
  Let $\gcd(204,391)=n$.  
  \begin{enumerate}
    \item
  Compute $n$.
\item
Find a solution of $204x+391y=n$.
  \end{enumerate}
\end{ex}

\begin{ex}
  Let $\gcd(a,b)=n$.
  \begin{enumerate}
    \item
If $k\divides\ell$ and $\ell\divides2k$, then
$\size{\ell}\in\{\size{k},\size{2k}\}$. 
\item
Show $\gcd(a+b,a-b)\in\{n,2n\}$.
\item
Find an example for each possibility.
\item
$\gcd(2a+3b,3a+4b)=n$.
\item
Solve $\gcd(ax+by,az+bw)=n$.
  \end{enumerate}
\end{ex}

\begin{ex}
  $\gcd(a,b)\divides\lcm(a,b)$. 
\end{ex}

\begin{ex}
  When are $\gcd(a,b)$ and $\lcm(a,b)$ the same?
\end{ex}

\begin{ex}
The binary operation $(x,y)\mapsto\gcd(x,y)$ on $\N\setminus\{0\}$ is
  commutative and associative.
\end{ex}

\begin{ex}
  The co-prime relation on $\N\setminus\{0\}$, namely
  \begin{equation*}
  \{(x,y)\in\N\setminus\{0\}\colon\gcd(x,y)=1\}
  \end{equation*}
---is it reflexive?
  irreflexive? symmetric?  anti-symmetric?  transitive?
\end{ex}

\begin{ex}
  Give complete solutions, or show that they do not exist, for:
  \begin{enumerate}
    \item
$14x-56y=34$;
\item
$10x+11y=12$.
  \end{enumerate}
\end{ex}

\begin{ex}
  I have some 1-YTL pieces and some 50- and 25-YKr pieces: 16 coins in
  all.  They make 6 YTL.
  How many coins of each denomination have I got?
\end{ex}

\def\cprime{$'$}
\begin{thebibliography}{1}

\bibitem{Burton}
David~M. Burton.
\newblock {\em Elementary Number Theory}.
\newblock McGraw-Hill, Boston, sixth edition, 2007.

\bibitem{DPfnth}
David Pierce.
\newblock Foundations of number-theory.
\newblock \url{http://www.math.metu.edu.tr/~dpierce/courses/365/}.
\newblock 4~pp.

\end{thebibliography}


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

%\layout


\end{document}