\documentclass[%
version=last,%
a5paper,
10pt,%
%headings=small,%
twoside,%
reqno,%
parskip=half,%
%draft=false,%
draft=true,%
%DIV=classic,%
DIV=10,%
%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}
\allowdisplaybreaks
\newcommand{\N}{\mathbb N}
\DeclareMathOperator{\lcm}{lcm}
%\newcommand{\ephi}{\upphi}
\newcommand{\size}[1]{\lvert#1\rvert}

%\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*{EL}{Euclid's Lemma}
\newtheorem*{FTh}{Fundamental Theorem of Arithmetic}
\newtheorem*{MITh}{M\"obius Inversion Theorem}
\newtheorem*{CRT}{Chinese Remainder Theorem}
\newtheorem*{ET}{Euler's 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{document}
\title{Number theory summary II}
\subtitle{MAT 221, fall 2014} 
\date{December 22, 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

%Exercises were given in class on December 1, 8, \&\ 15.
%In these notes, 
$\N=\{1,2,3,\dots\}$, the set of \textbf{natural numbers,}
and letters will range over this set or else %(if said so) 
the set $\Z$ %(which is $\N\cup\{0\}\cup\{-x\colon x\in\N\}$)
of \textbf{integers.}
In $\N$ or $\Z$, the expression
\begin{equation*}
  a\divides b
\end{equation*}
means $a$ \textbf{divides} $b$,
and $b$ is a \textbf{multiple} of $a$,
that is, for some $q$, $aq=b$.
In this case, in $\N$, $a\leq b$.

\begin{divthm}
  If $a\ndivides b$, then for some unique $q$ and $r$,
  \begin{equation*}
    b=aq+r\And r<a.
  \end{equation*}
\end{divthm}

Since $a$ and $b$ have a common multiple (namely $ab$),
they have a \textbf{least common multiple} (by the Well Ordering Theorem),
denoted by
\begin{equation*}
  \lcm(a,b).
\end{equation*}
Since they have a common divisor (namely $1$),
and all common divisors are less than or equal to $\min\{a,b\}$,
the numbers $a$ and $b$ have a \textbf{greatest common divisor,} denoted by
\begin{equation*}
  \gcd(a,b);
\end{equation*}
this can be found by the \textbf{Euclidean Algorithm.}

\begin{theorem}%\mbox{}
  \begin{enumerate}
    \item
$ab=\gcd(a,b)\cdot\lcm(a,b)$.
\item
Every common divisor of $a$ and $b$ divides $\gcd(a,b)$.
\item
$\lcm(a,b)$ divides every common multiple of $a$ and $b$.
  \end{enumerate}
\end{theorem}

\begin{EL}
  If $a\divides bc$, but $\gcd(a,b)=1$, then $a\divides c$.
\end{EL}

\begin{proof}
  By the Euclidean Algorithm, in $\Z$ we can solve
  \begin{equation*}
    ax+by=\gcd(a,b).
  \end{equation*}
If $ax+by=1$ and $a\divides bc$, then $acx+bcy=c$ and so $a\divides c$.
\end{proof}

The letter $p$ always denotes a \textbf{prime number.}
If $p\divides a$, we may define
\begin{equation*}
  a(p)=\max\{n\colon p^n\divides a\}.
\end{equation*}
(The existence of this maximum can be proved 
by contradiction and the Well Ordering Theorem.)
If $p\ndivides a$, we may let $a(p)=0$.
If always $a(p)\leq1$, then $a$ is \textbf{squarefree.}

\begin{FTh}
%$a=\prod_pp^{a(p)}$, that is,
Every natural number is a product of primes
in only one way:
\begin{equation*}
  a=\prod_pp^{a(p)}.
\end{equation*}
\end{FTh}

\begin{proof}
  By the Strong Induction Theorem,
every natural number is a product of primes;
by Euclid's Lemma, it is so in only one way.
\end{proof}

Thus
\begin{align*}
  \gcd(a,b)&=\prod_pp^{\min\{a(p),b(p)\}},&
\lcm(a,b)&=\prod_pp^{\max\{a(p),b(p)\}}.
\end{align*}
% $\gcd(a,b)=\prod_pp^{\min\{a(p),b(p)\}}$ 
%and $\lcm(a,b)=\prod_pp^{\max\{a(p),b(p)\}}$.

A \textbf{number-theoretic function} or \textbf{arithmetic function}
is a function with domain $\N$.
We define four of them:
\begin{itemize}
\item 
$\uptau(a)=\sum_{d\divides a}1$, the number of divisors of $a$;
\item
$\upsigma(a)=\sum_{d\divides a}d$, the sum of the divisors of $a$;
\item
$\upphi(a)=\bigl|\{x\in\N\colon x\leq n\And\gcd(x,n)=1\}\bigr|$;
\item
$\upmu(a)=\prod_{p\divides a}(-1)$, if $a$ is squarefree; otherwise $\upmu(a)=0$.
\end{itemize}
An arithmetic function $F$ is \textbf{multiplicative} if
\begin{equation*}
  \gcd(a,b)=1\implies F(ab)=F(a)\cdot F(b).
\end{equation*}

\begin{theorem}
$\uptau$ and $\upsigma$ are multiplicative, and
  \begin{align*}
\uptau(a)&=\prod_{p\divides a}(a(p)+1),&
    \upsigma(a)&
=\prod_{p\divides a}\sum_{k=0}^{a(p)}p^k
=\prod_{p\divides a}\frac{p^{a(p)+1}-1}{p-1}.
  \end{align*}
\end{theorem}

A number $a$ is \textbf{perfect} if $\upsigma(a)=2a$.
Examples include $6$, $28$, $496$, and $8128$.
A \textbf{Mersenne prime} is a prime of the form $2^n-1$, 
which is $\sum_{k=0}^{n-1}2^k$.
Examples include $3$, $7$, $31$, and $127$.

\begin{theorem}%[Euclid \&\ Euler]
  The even perfect numbers are just the numbers $p\cdot(p+1)/2$,
%  \begin{equation*}
%  \frac{p+1}2\cdot p,
%  \end{equation*}
  where $p$ is a Mersenne prime.
\end{theorem}

\begin{MITh}
For arithmetic functions $F$ and $G$,
\begin{equation*}
G(a)=\sum_{d\divides a}F(d)
\implies
F(a)=\sum_{d\divides a}\upmu(d)\cdot G\left(\frac ad\right).
\end{equation*}
\end{MITh}

\begin{proof}
  First prove the special case where 
$F(a)=  \begin{cases}
    1,&\text{ if $a=1$},\\
0,&\text{ if $a>1$}.
  \end{cases}$
\end{proof}

\begin{theorem}
 $\upphi$ is multiplicative, and
  \begin{equation*}
\upphi(a)
=a\cdot\displaystyle\prod_{p\divides a}\left(1-\displaystyle\frac1p\right)
=\prod_{p\divides a}\left(p^{a(p)}-p^{a(p)-1}\right).
  \end{equation*}
In particular, $\upphi(p^r)=p^r-p^{r-1}$.
\end{theorem}

\begin{proof}
  First show $\sum_{d\divides a}\upphi(d)=a$.
Then by M\"obius Inversion,
\begin{equation*}
  \upphi(a)
=a\cdot\sum_{d\divides a}\frac{\upmu(d)}d
=a\cdot\sum_{d\divides p_1\cdots p_r}\frac{\upmu(d)}d,
\end{equation*}
where $p_1\cdots p_r=\prod_{p\divides a}p$.
By induction on $r$,
\begin{equation*}
  \sum_{d\divides p_1\cdots p_r}\frac{\upmu(d)}d
=\prod_{n=1}^r\left(1-\frac1{p_n}\right).\qedhere
\end{equation*}
\end{proof}

For arbitrary \emph{integers} $a$ and $b$, 
if $m\in\N$ and $m\divides a-b$, we say $a$ and $b$ are 
\textbf{congruent} to one another, writing
\begin{equation*}
  a\equiv b\pmod m.
\end{equation*}

\begin{fermat}
  $a^p\equiv a\pmod p$, and if $p\ndivides a$, then
  \begin{equation*}
  a^{p-1}\equiv1\pmod p.
  \end{equation*}
\end{fermat}

\begin{proof}
  By induction on $a$, or as a special case of the following.
\end{proof}

\begin{ET}
  If $\gcd(a,m)=1$, then
  \begin{equation*}
a^{\upphi(m)}\equiv1\pmod m.
  \end{equation*}
\end{ET}

\begin{proof}
  If $\{x\in\N\colon x\leq m\And\gcd(x,m)=1\}=\{b_1,\dots,b_{\upphi(m)}\}$,
then $\prod_{k=1}^{\upphi(m)}(ab_k)
\equiv\prod_{k=1}^{\upphi(m)}b_k\pmod m$.
\end{proof}

\begin{CRT}
  If $\gcd(m,n)=1$,
then every system
\begin{align*}
  x&\equiv a\pmod m,&
%&\&&
x&\equiv b\pmod n
\end{align*}
is uniquely soluble \emph{modulo} $mn$,
every solution being congruent to
\begin{equation*}
anc+bmd, 
\end{equation*}
where
$nc\equiv1\pmod m$ and $md\equiv1\pmod n$.
\end{CRT}

\end{document}