\documentclass[%
version=last,%
a5paper,
10pt,%
%headings=small,%
twoside,%
reqno,%
parskip=half,%
%draft=false,%
draft=true,%
%DIV=classic,%
DIV=12,%
%headinclude=true,%
%titlepage=true,%
pagesize]
{scrartcl}

\usepackage{verbatim}

\begin{comment}
  

\usepackage[headsepline]{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\ohead{\pagemark}
\ihead{Number theory summary}

\end{comment}

\usepackage{hfoldsty,url,relsize}
\usepackage[neverdecrease]{paralist}

\usepackage{amsmath}
\newcommand{\N}{\mathbb N}
\newcommand{\included}{\subseteq}
\newcommand{\Forall}[1]{\forall#1\;}
\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\lto}{\Rightarrow}
\newcommand{\fib}[1]{\mathrm F_{#1}}
\newcommand{\divides}{\mid}
\newcommand{\ndivides}{\nmid}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Zmod}[1][n]{\Z_{#1}}

\usepackage{amssymb,upgreek,amsthm}

\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}

\newtheorem*{theorem}{Theorem}
\newtheorem*{recthm}{Recursion Theorem}
\newtheorem*{strind}{Strong Induction Theorem}
\newtheorem*{wo}{Well Ordering Theorem}
\newtheorem*{divthm}{Division Theorem}
\newtheorem*{fermat}{Fermat's Theorem}

\begin{comment}
  

\usepackage{amsmath,amsthm,amssymb,upgreek}
\newcommand{\ephi}{\upphi}
\newcommand{\size}[1]{\lvert#1\rvert}
\newcommand{\ord}[2][p]{\operatorname{ord}_{#1}(#2)}
\newcommand{\mpsi}[2][p]{\uppsi_{#1}(#2)}


\newtheorem{problem}{Problem}
\newtheorem*{bonus}{Bonus}
\theoremstyle{remark}
\theoremstyle{definition}
\newtheorem*{solution}{Solution}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\end{comment}

\begin{document}
\title{Number theory summary}
\subtitle{MAT 221, fall 2014} 
\date{November 3, 2014}
\author{David Pierce}
\publishers{%Mathematics Department, MSGS\"U\\
%Mimar Sinan Fine Arts University, Istanbul\\
%\url{dpierce@msgsu.edu.tr}\\
%\smaller
\url{http://
mat.msgsu.edu.tr/~dpierce/Dersler/
%Number-theory/
}}

\maketitle

The set $\N$ of \textbf{natural numbers} 
is postulated to be such that
\begin{enumerate}[(i)]
  \item
$1\in\N$;
\item
$x\mapsto x'\colon\N\to\N$ 
(where $x'$ is called the \textbf{successor} of $x$);
  \item
\textbf{proof by induction} is possible:
If $A\included\N$, and 
\begin{compactitem}
  \item
$1\in A$,
\item
for all $n$ in $\N$, if $n\in A$, then $n'\in A$,
\end{compactitem}
then \textbf{by induction} $A=\N$.
\end{enumerate}

\begin{theorem}
The binary operations $+$ and $\cdot$ can be defined on $\N$ by
\begin{align*}
  x+1&=x',&x+y'&=(x+y)',\\
x\cdot1&=x,&x\cdot y'&=x\cdot y+x,
\end{align*}
\end{theorem}

(Proof not required.)

\begin{theorem}
$+$ and $\cdot$ are commutative and associative, 
and $\cdot$ distributes over $+$.
\end{theorem}

We postulate now
\begin{enumerate}[(i)]\setcounter{enumi}3
\item
  $1$ is not a successor ($\Forall x1\neq x'$),
\item
$x\mapsto x'$ is injective ($\Forall x\Forall y(x'=y'\lto x=y)$).
\end{enumerate}

\begin{recthm}
If $A$ is a set, and
\begin{align*}
  b&\in A,&
f&\colon A\times\N\to A,
\end{align*}
then there is a unique function $g$ from $\N$ to $A$ such that
\begin{compactitem}
  \item
$g(1)=b$,
\item
for all $n$ in $\N$, $g(n+1)=f(g(n),n)$.
\end{compactitem}
\end{recthm}

(Proof not required.)
We now obtain some new operations
by the \textbf{recursive definitions}
\begin{align*}
            x^1&=x,    &                x^{n+1}&=x^n\cdot x,\\
             1!&=1,    &               (n+1)!&=n!\cdot(n+1),\\
  \sum_{k=1}^1a_k&=a_1,  &    \sum_{k=1}^{n+1}a_k&=\sum_{k=1}^na_k+a_{n+1},\\
 \prod_{k=1}^1a_k&=a_1,  &   \prod_{k=1}^{n+1}a_k&=\prod_{k=1}^na_k\cdot a_{n+1},\\
(\fib 1,\fib 2)&=(1,1),&(\fib{n+1},\fib{n+2})&=(\fib{n+1},\fib n+\fib{n+1}).
\end{align*}
We introduce $0$ such that $0\notin\N$, but $0'=1$;
and we let
\begin{equation*}
  \N\cup\{0\}=\upomega.
\end{equation*}
Then the structure $(\upomega,0,{}')$, like $(\N,1,{}')$,
satisfies Postulates (i--v), which are called the \textbf{Peano Axioms.}
We define
\begin{align*}
x+0&=x,&
x\cdot0&=0,&
x^0&=1,&
0!&=1,&
\sum_{k=1}^0a_k&=0,&
\prod_{k=1}^0a_k&=1.
\end{align*}
By a double recursion, we define
\begin{align*}
  \binom 00&=1,&\binom 0{k+1}&=0,&
\binom{n+1}0&=1,&\binom{n+1}{k+1}&=\binom nk+\binom n{k+1}.
\end{align*}
By induction, we can prove results like
\begin{enumerate}[1)]
\item
$\sum_{k=1}^n1=n$,\
\item
$2\cdot\sum_{k=1}^nk=n\cdot(n+1)$,
\item
$6\cdot\sum_{k=1}^nk^2=n\cdot(n+1)\cdot(2n+1)$,
%\item $4\cdot\sum_{k=1}^nk^3=n^2\cdot(n+1)^2$,
\item
$\sum_{k=0}^n(2k+1)=(n+1)^2$,
\item
$1+\sum_{k=1}^n\fib k=\fib{n+2}$,
\item
if $k+\ell=n$, 
then
\begin{align*}
  \binom nk&=\binom n{\ell},&
\binom nk\cdot k!\cdot\ell!&=n!.
\end{align*}
\end{enumerate}
\begin{comment}
  

\begin{gather}
  \sum_{k=1}^n1=n,\\
2\cdot\sum_{k=1}^nk=n\cdot(n+1),\\
6\cdot\sum_{k=1}^nk^2=n\cdot(n+1)\cdot(2n+1),\\
4\cdot\sum_{k=1}^nk^3=n^2\cdot(n+1)^2,\\
\sum_{k=0}^n(2k+1)=(n+1)^2,\\
1+\sum_{k=1}^n\fib k=\fib{n+2}.
\end{gather}


\end{comment}
On $\N$, we write $x<y$ and say $x$ \textbf{is less than} $y$ 
if for some $z$ in $\N$, $x+z=y$.
We prove that $<$ is an 
\textbf{irreflexive} and \textbf{transitive} relation on $\N$;
thus it is an \textbf{ordering} of $\N$.
It respects also the \textbf{trichotomy} law, 
so it is a \textbf{linear} ordering of $\N$.
We write $x\leq y$ to mean $x<y$ or $x=y$.
Then by definition $0\leq x$ for all $x$ in $\upomega$.
Now can prove by induction that, 
for example,
for all $n$ in $\upomega$,
\begin{align*}
  2^n&\geq 2n,&2^n+1&\geq n^2.
\end{align*}
If $x\leq y$, then the $z$ in $\upomega$ 
such that $x+z=y$ is unique and is denoted by $y-x$.
Now we can state and prove the \textbf{Binomial Theorem:}
\begin{equation*}
(x+y)^n=\sum_{k=0}^n\binom nkx^ky^{n-k}.
\end{equation*}
We use the notation $\{x\in\N\colon x<n\}=\{1,\dots,n-1\}$.

\begin{strind}
%We show that \textbf{proof by strong induction} is possible in $\N$:
if $A\included\N$ and
\begin{compactitem}
  \item
for all $n$ in $\N$, if $\{1,\dots,n-1\}\included A$, then $n\in A$,
\end{compactitem}
then $A=\N$.
\end{strind}

In $\upomega$, the notation $k\divides n$ means that, 
for some $\ell$, $k\cdot\ell=n$.
In this case, $k$ is a \textbf{divisor} or \textbf{factor} of $n$.
If $p>1$, and the only factors of $p$ are $1$ and $p$, 
then $p$ is called \textbf{prime.}
If $n>1$, but $n$ is not prime, then it is \textbf{composite.}
By strong induction, every natural number greater than $1$ has a prime factor.
Similarly, every natural number $n$ has a \textbf{prime factorization:} 
there is $m$ in $\upomega$
and a function $k\mapsto p_k$ on $\{1,\dots,m\}$ 
such that each $p_k$ is prime and
$n=\prod_{k=1}^mp_k$.

\begin{wo}
%We show that $\N$ is \textbf{well ordered:} 
Each \emph{nonempty} subset of $\upomega$ has a least element.
\end{wo}

\begin{divthm}
For all $m$ in $\N$ and $n$ in $\upomega$, 
there are unique $q$ and $r$ in $\upomega$ such that
\begin{equation*}
  n=m\cdot q+r\And 0\leq r<m.
\end{equation*}
\end{divthm}

Here $r$ is the \textbf{remainder} when $n$ is divided by $m$.
Given $a_0$ and $a_1$ in $\N$, where $a_0>a_1$,
we find their \textbf{greatest common divisor} 
by the \textbf{Euclidean Algorithm:}
if $a_{k+1}>0$, let $a_{k+2}$ be the remainder when $a_n$ is divided by $a_{k+1}$.
For some least $n$, $a_{n+1}$ will be $0$; 
and then $a_n$ is the greatest common divisor of $a_0$ and $a_1$.

If $n\in\N$,
and $n\divides a-b$ or $n\divides b-a$,
we say $a$ and $b$ are \textbf{congruent \emph{modulo}} $n$,
writing
\begin{equation*}
  a\equiv b\pmod n,
\end{equation*}
or $a\equiv b$ if $n$ is understood.
Congruence \emph{modulo} $n$ is an \textbf{equivalence relation}
(it is \textbf{reflexive, symmetric,} and \textbf{transitive}).
The congruence class of $a$ \emph{modulo} $n$ can be denoted by $\bar a$;
the set of all congruence classes, by $\Zmod$.
Then $\Zmod=\{\bar 1,\dots,\bar n\}$.
Also, if $x\equiv y$, then $x'\equiv y'$.
Thus we can define $(\bar x)'=\overline{x'}$.
The structure $(\Zmod,\bar 1,{}')$ allows proofs by induction.
Therefore
\begin{equation*}
  a\equiv b\And c\equiv d\implies a+c\equiv b+d\And a\cdot c\equiv b\cdot d.
\end{equation*}
However, $1\equiv 4\And 2^1\not\equiv 2^4\pmod3$.
This shows that recursive definitions may require more than induction.


\begin{comment}
  

\begin{fermat}
If $p$ is prime, then for all $a$,
\begin{equation*}
  a^p\equiv a\pmod p.
\end{equation*}
\end{fermat}

\end{comment}

\end{document}