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

%\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
%\usepackage{pstricks}

\usepackage{hfoldsty,url}
\usepackage[neverdecrease]{paralist}
\usepackage{amsmath,amsthm,amssymb,upgreek}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\divides}{\mid}
\newcommand{\ndivides}{\nmid}
\newcommand{\ephi}{\upphi}
\newcommand{\size}[1]{\lvert#1\rvert}
\newcommand{\ord}[2][p]{\operatorname{ord}_{#1}(#2)}
\newcommand{\mpsi}[2][p]{\uppsi_{#1}(#2)}

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

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

\begin{document}
\title{Summary of MAT 221% (Number Theory)
} 
\date{January 2, 2013}
\author{David Pierce}
\publishers{%Mathematics Department, MSGS\"U\\
%Mimar Sinan Fine Arts University, Istanbul\\
\url{dpierce@msgsu.edu.tr}\\
\url{http://mat.msgsu.edu.tr/~dpierce/Dersler/Number-theory/}}

\maketitle

Let $\N=\{1,2,3,\dots\}=\{x\in\Z\colon x>0\}$.  On $\N$ (or more generally on $\{n,n+1,n+2,\dots\}$), we can:
\begin{compactitem}
\item
define functions by \textbf{recursion} (so that, if $A$ is some set, $c\in A$, and $f\colon A\to A$, then there is a unique function $k\mapsto a_k$ on $\N$ such that $a_1=c$ and, for all $k$ in $\N$, $a_{k+1}=f(a_k)$; if also $g\colon A\times\N\to A$, then there is a unique function $k\mapsto b_k$ on $\N$ such that $b_1=c$ and, for all $k$ in $\N$, $b_{k+1}=g(b_k,k)$);
\item
prove theorems by \textbf{induction;}
\item
prove theorems by \textbf{strong induction.}
\end{compactitem}
For example, by strong induction, every natural number other than $1$ has a prime factor:  For, suppose $n\in\N$, and every element of $\{x\in\N\colon 1<x<n\}$ has a prime factor.  Either $n$ is $1$, or $n$ is prime, or $n$ has a factor $k$ such that $1<k<n$.  In the last case, by the strong inductive hypothesis, $k$ has a prime factor; but this factor is then a factor of $n$ too.
%  Thus in all cases $n$ is $1$ or has a prime factor.  This proves the claim.

We have the \textbf{Euclidean algorithm} for finding the greatest common divisor of two integers (not both of which are $0$).  If $\gcd(a,b)=d$, then we can also use the algorithm to solve
\begin{equation*}
ax+by=d.
\end{equation*}
If $\gcd(a,n)=1$, then $a\cdot a^{-1}\equiv 1\pmod n$ for some number $a^{-1}$, which can be found by means of the Euclidean algorithm.

If $n\divides ab$ and $\gcd(n,a)=1$, then $n\divides b$.  In particular, if $p\divides ab$, but $p\ndivides a$, then $p\divides b$.  
This can be used to prove the \textbf{Fundamental Theorem of Arithmetic.}

We can solve all \textbf{linear} congruences, that is, congruences of the form
\begin{equation*}
ax\equiv b\pmod n.
\end{equation*}
By the \textbf{Chinese Remainder Theorem,}
every linear system
\begin{align*}
x&\equiv a_1\pmod{n_1},&&\dots,&x\equiv a_k\pmod{n_k},
\end{align*}
has a unique solution (which we can find) \emph{modulo} $n_1\dotsm n_k$,
assuming the moduli $n_i$ are pairwise coprime.   (What if they are not?)

An even number $n$ is \textbf{perfect,} that is, $\sum_{d\divides n}=2n$, if and only if
\begin{equation*}
n=2^{k-1}\cdot(2^k-1)
\end{equation*}
for some $k$ such that $2^k-1$ is prime.

If $n>0$, we let
\begin{align*}
\Z_n&=\{0,1,\dots,n-1\},&\Z_n{}^{\times}&=\{x\in\Z_n\colon\gcd(x,n)=1\}.
\end{align*}
Then by definition
\begin{equation*}
\ephi(n)=\size{\Z_n{}^{\times}}.
\end{equation*}
The values of $\ephi$ (the \textbf{Euler phi-function}) can be found by two rules:
\begin{compactenum}
\item
$\ephi(ab)=\ephi(a)\cdot\ephi(b)$, if $\gcd(a,b)=1$.
\item
$\ephi(p^{k+1})=p^{k+1}-p^k=p^{k+1}\cdot(1-1/p)$.
\end{compactenum}
\textbf{Euler's Theorem} is
\begin{equation*}
\gcd(a,n)=1\implies a^{\phi(n)}\equiv 1\pmod n.
\end{equation*}
(\textbf{Fermat's Theorem} is the special case when $n=p$.)  The proof uses that if $\gcd(a,n)=1$, then
\begin{equation*}
\prod_{x\in\Z_n{}^{\times}}x
\equiv \prod_{x\in\Z_n{}^{\times}}(ax)
\equiv a^{\phi(n)}\cdot\prod_{x\in\Z_n{}^{\times}}x\pmod n.
\end{equation*}
Compare to the proof of \textbf{Wilson's Theorem:}
\begin{equation*}
(p-1)!
\equiv-1\cdot 2\cdot 2^{-1}\dotsm
%\cdot 3\cdot 3^{-1}\dotsm\frac{p-1}2\cdot\Bigl(\frac{p-1}2\Bigr)^{-1}
\equiv-1\pmod p.
\end{equation*}

We now have a method for computing powers \emph{modulo} $n$, that is, for solving $a^k\equiv x\pmod n$.  If $0<k<\ephi(n)$, we can find $b_1$, \dots, $b_m$ such that
\begin{align*}
0&\leq b_1<\dots<b_m,&
k&=2^{b_1}+\dots+2^{b_m};
\end{align*}
and then $a^k$ is easily computed as $a^{2^{b_1}}\dotsm a^{2^{b_m}}$.

\emph{Henceforth $p$ is an odd prime.}
With the usual quadratic formula, we can solve \textbf{quadratic} congruences
\begin{align*}
ax^2+bx+c\equiv0\pmod p,
\end{align*}
at least if we have a way to find square roots \emph{modulo} $p$, when they exist.
If the square root of $d$ \emph{modulo} $p$ does exist, that is,
if $x^2\equiv d\pmod p$ is soluble, then $d$ is called a \textbf{quadratic residue} of $p$. 

If $\gcd(a,n)=1$, then $a$ has an \textbf{order} \emph{modulo} $n$, namely the least positive exponent $k$ such that $a^k\equiv 1\pmod n$.  We may denote this exponent by
\begin{equation*}
\ord[n]a.
\end{equation*}
Then $\ord[n]a\divides\ephi(n)$.
For example, by the computations
\begin{equation*}
\begin{array}{|c*{8}{|r}|}\hline
  k         &1&2&3& 4& 5& 6& 7&8\\\hline
2^k\pmod{17}&2&4&8&-1&-2&-4&-8&1\\\hline
\end{array}
\end{equation*}
we have $\ord[17]2=8$.  Likewise,
$\ord[17]3=16$, by the following.
\begin{equation*}
  \begin{array}{|c*{8}{|r}|}\hline
    k&1&2&3&4&5&6&7&8\\\hline
3^k\pmod{17}&3&-8&-7&-4&5&-2&-6&-1\\\hline\hline
k&9&10&11&12&13&14&15&16\\\hline
3^k\pmod{17}&-3&8&7&4&-5&2&6&1\\\hline
  \end{array}
\end{equation*}
In general, $a$ is called a \textbf{primitive root} of $n$ of $\ord a=\ephi(n)$.  For example, $3$ is a primitive root of $17$, but $2$ is not.  Also, $8$ has no primitive root, since $\ephi(8)=4$, but $3^2\equiv5^2\equiv7^2\equiv1\pmod8$.
When they exist, primitive roots are found by trial; there is no formula for computing them.

Suppose $a$ is a primitive root of $p$.  Then
\begin{equation*}
\ord{a^k}=\frac{p-1}{\gcd(k,p-1)}.
\end{equation*}
This gives us the following from the computations above:
\begin{equation*}
  \begin{array}{|c*{8}{|r}|l|}\hline
           k      & 0&14& 1&12& 5&15&11&10&\pmod{16}\\\hline
         3^k      & 1& 2& 3& 4& 5& 6& 7& 8&\pmod{17}\\\hline
\ord[17]{3^k}     & 1& 8&16& 4&16&16&16& 8&\\\hline
    \gcd(k,16)    &16& 2& 1& 4& 1& 1& 1& 2&\\\hline\hline
            k+8   & 8& 6& 9& 4&13& 7& 3& 2&\pmod{16}\\\hline
         3^{k+8}  &16&15&14&13&12&11&10& 9&\pmod{17}\\\hline
\ord[17]{3^{k+8}} & 2& 8&16& 4&16&16&16& 8&\\\hline
\gcd(k+8,16)      & 8& 2& 1& 4& 1& 1& 1& 2&\\\hline
  \end{array}
\end{equation*}
In general, if $\gcd(d,n)=1$, let
\begin{equation*}
\mpsi[n]d=\size{\{x\in\Z_n{}^{\times}\colon\ord[n]x=d\}}.
\end{equation*}
For example, from the last table we have the following.
\begin{equation*}
\begin{array}{*6{|c}|}\hline
      d &1&2&4&8&16\\\hline
\mpsi[17]d &1&1&2&4& 8\\\hline
\ephi(d)&1&1&2&4& 8\\\hline
\end{array}
\end{equation*}
In fact it is always true that\footnote{The proof is that $\sum_{d\divides p-1}\ephi(d)=p-1=\sum_{d\divides p-1}\mpsi d$ and $\mpsi d\leq\ephi(d)$; but we have not seen all of the details.}
\begin{equation*}
\mpsi d=\ephi(d).
\end{equation*}
In particular, since $\ephi(p-1)\geq1$, $p$ must have a primitive root.\footnote{Only $2$, $4$, $p^k$, and $2p^k$ have primitive roots.}

If $a$ is a primitive root of $p$, then the quadratic residues of $p$ are the \emph{even} powers of $a$ (that is, the powers $a^k$ such that $k$ is even).

\end{document}