\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

\begin{center}

THEORY OF NUMBERS

CONGRUENCES

\end{center}

A reduced set of residues (mod $m$) is a set of $\phi(m)$ numbers,
one from each of the residue classes relatively prime to $m$.

e.g. $m=10$ C.S.R.=$0\ \pm1\ \pm2\ \pm3\ \pm4\ \pm5$ R.S.R=$\pm1\
\pm3$

\begin{description}

\item[Theorem]
Suppose $(k,\ m)=1$ then if $x$ runs through a C.S.R. or R.S.R. so
does $kx$

\item[Proof]

\begin{description}

\item[(i)]
$kx$ takes $m$ values and no two are congruent mod $m$ since
$kx_1\equiv kx_2\Rightarrow x_1=x_2$ as $(k,\ m)=1$

\item[(ii)]
$kx$ takes $\phi(m)$ values, mutually uncongruent mod $m$, as $m$
(i), and $(kx,\ m)=(x,\ m)=1$ as $(k,\ m)=1$.

\end{description}

\item[Theorem (Fermat-Euler)]
$a^{\phi(m)}=1$ mod $m$ if $(a,\ m)=1$

\item[Proof]
Let $x_1,x_2\ldots x_{\phi(m)}$ be a R.S.R. mod $m$. By the
previous theorem, $ax_1,ax_2,\ldots ax_{\phi(m)}$ is a R.S.R mod
$m$. Hence these numbers are congruent to $x_1 x_2\ldots
x_{\phi(m)}$ in some order. Therefore $$ax_1ax_2\ldots
ax_{\phi(m)}\equiv x_1x_2\ldots x_{\phi(m)}\ (m)$$

Therefore $a^{\phi(m)}\equiv1$

\item[Corollary]
$a^{p-1}\equiv1$ mod $p$ if $a\not\equiv0$ mod $p$

$a^p\equiv a$ mod $p$ for all $a$.

\item[Linear congruences]
$ax\equiv b$ mod $m\ (a\not\equiv0$ mod $m)$. N.S.C. for
solubility are the N.S.C. for integral solutions $x,\ y$ of
$ax-my=b$ i.e. $(a,\ m)|b$.

\item[General solution]
Suppose $x_0,\ y_0$ is a particular solution of $ax-my=b$ and $x,\
y$ the general solutions therefore

\begin{equation}a(x_0-x)-m(y_0-y)=0\end{equation}

therefore $m'|x-x_0$ where $m'=\frac{m}{(a,\ m)}$ and $a'|y-y_0$
where $a'=\frac{a}{(a,\ m)}$

therefore

$x=x\_0+m't\\y=y_0+a'l$

Substituting $m$(1) gives $t=l$, therefore

$x=x_0+m't\\ y=y_0+a't$

giving different solutions for $t=1,2,\ldots \frac{m}{m'}$, all
other solutions belonging to one of these residue classes mod $m$
therefore $\exists (a,\ m)$ solutions.

\item[The Chinese Remainder Theorem]
If every pair from $(m_1,\ldots,m_r)$ is relatively prime, the
simultaneous congruences

$x\equiv a_1$ mod $m_1,\ldots x\equiv a_r$ mod $m_r$

have a solution which is unique mod $m_1,\ldots m_r$.

\item[Proof]
Put $$M_j=\frac{\prod_{i=1}^r m_i}{m_j}\ j=1,2,\ldots,r$$

Choose $\xi_j$ such that $M_j\xi_j\equiv a_j$ mod $m_j$

This is possible since $(M_j,\ m_j)=1$. Note that $M_j\xi_j=0$ mod
$m_i,\ i\neq j$

Take $x=M_1\xi_1+M_2\xi_2+\ldots+M_r\xi_r$. Then $x\equiv a_j$ mod
$m_j\ j=1,2,\ldots r$.

Suppose $x_1,\ x_2$ are solutions. Then $x_1\equiv a_i$ mod $m_i\
i=1,2,\ldots r,\ x_2\equiv a_i$ mod $m_i\ i=1,2,\ldots,r$.
Therefore $x_1-x_2\equiv 0$ mod $m_i,\ i=1,2,\ldots r$ therefore
$x_1-x_2\equiv 0$ mod $m_1m_2\ldots m_r$.

\item[Corollary]
The congruence $P(x)\equiv 0$ mod $m$ is equivalent to the
simultaneous congruences $P(x)\equiv 0$ mod $p_i^{r_i}\
i=1,2,\ldots n$.

\item[Theorem]
Suppose $(a,\ b)=1$.

Suppose $x$ runs through a
$\left\{\begin{array}{c}C.S.R.\\R.S.R\end{array}\right\}$ mod $a$

 Suppose $y$ runs through a
$\left\{\begin{array}{c}C.S.R.\\R.S.R\end{array}\right\}$ mod $b$

 Then $bx+ay$ runs through a
$\left\{\begin{array}{c}C.S.R.\\R.S.R\end{array}\right\}$ mod
$ab$.

\item[Proof]
C.S.R

There are $ab$ values of $bx+ay$ and no two are congruent mod
$ab$, for if $bx+ay\equiv bx'+ay'$ mod $ab$ then $bx\equiv bx'$
mod $a$ and $ay=ay'$ mod $b$ since $(ab)=1$ therefore $x=x'$ mod
$a$ and $y=y'$ mod $b$.

R.S.R

No two values of $bx+ay$ are congruent mod $ab$ as above. All
values of $bx+ay$ are relatively prime to $ab$, for suppose
$p|ax+by|$ and $p|ab$. Then $p|a$ or $p|b$ so suppose $p|a$.
$p\not| b$ as $(a,\ b)=1$ therefore $p|x$. But $(a,\ x)=1$ as
$x\in$ R.S.R. mod $a$

Conversely every number $m$ relatively prime to $ab$ is congruent
to some $bx+ay$ mod $ab$ for if $(ab,\ m)=1$ choose $x,\ y$ so
that

$\begin{array}{ll}bx\equiv m& \textrm{ mod }a\\ay\equiv m&\textrm{
mod }b\end{array}\left\{\begin{array}{c}\textrm{unique as $(a,\
b)=1$ and $(a,\ x)=1$}\\\textrm{unique as $(a,\ b)=1$ and $(b,\
y)=1$.}\end{array}\right.$

Therefore $bx+ay\equiv m$ mod $a$ and mod $b$ and so mod $ab$ as
$(a,b)=1$.


\item[Corollary]
$\pi(a,\ b)=\phi(a)\phi(b)$ if $(a,\ b)=1$.

\item[Wilson's Theorem]
$p$ is prime $\Leftrightarrow (p-1)!\equiv -1$ mod $p$.

\item[Proof]

\begin{description}

\item[(i)]
$(p-1)!\equiv-1$ mod $p\Rightarrow (p-1)!+1=np$ for some integer
$n$.

Now none of the numbers $2,3,\ldots p-1$ divides $(p-1)!+1$, for
each of them leaves remainder 1 and so $2,3,\ldots p-1$ do not
divide $p$. So $p$ is prime.

\item[(ii)]
$p=2$ gives $1!\equiv-1$ mod $2$, $p=3$ gives $2!=-1$ mod 3.

Suppose $p>3$. For every $x\not\equiv0$ mod $p\exists$ a unique
$x'$ mod $p$ such that $xx'\equiv1$ mod $p$. If we also have
$x\equiv x'$ mod $p$ then $x^2\equiv1$ mod $p$.

i.e. $p|x^2-1$ i.e.$p|x-1$ or $x+1$ therefore $x\equiv \pm1$ mod
$p$.

Thus in the product $2,3,\ldots p-2$ the factors can be associated
in pairs, the product of each pair being $\equiv1$ mod $p$.

Hence $(p-2)!\equiv1$ mod $p$ therefore $(p-1)!\equiv p-1\equiv-1$
mod $p$.

The residue classes mod $p$ form a finite field.

\end{description}

\item[Definition]
Let $(a,m)=1$. Suppose $f$ is the least positive integer for which
$a^f\equiv1$ mod $m$. Then we say that $a$ belongs to the exponent
 $f$ mod $m$.

Note that $a^s\equiv1$ mod $m\Leftrightarrow f|s$

\begin{description}

\item[(i)]
$f|s\Rightarrow s=qf\\ a^s=(a^f)^q\equiv 1^q\equiv 1$ mod $m$.

\item[(ii)]
$a^s\equiv1$ mod $m\\ s=qf+r\ o\leq r<f$

Therefore $(a^f)^q.a^r\equiv1$ mod $m$

therefore $a^r\equiv1$ mod $m$

therefore $r=0$ by definition of $f$ and $sof|s$

In particular $f|\phi(m)$ since $a^{\phi(m)}\equiv1$ mod $m$.

\end{description}

\item[Theorem]
Let $p$ be prime and let $f$ be a divisor of $p-1$. Then among a
R.S.R. mod $p$ there are exactly $\phi(f)$ elements belonging to
the exponent $f$ mod $p$.

In particular there are $\pi(p-1)$ elements belonging to the
exponent $p-1$ mod $p$: sich an element is known as a primitive
root mod $p$.

\item[Proof]
Let $\psi(f)$ be the number of elements belonging to the exponent
$f$. We prove

\begin{description}

\item[(1)]
$\psi(f)=0$ or $\phi(f)$

Suppose $f|p-1$ and suppose $\psi(f)\neq 0$. Then $\exists a$,
belonging to exponent $f$. $1,a,a^2\ldots a^{f-1}$ are uncongruent
mod $p$, but all satisfy $x^f\equiv1$ mod $p$. So they are all
solutions of $x^f\equiv1$

Thus the numbers belonging to exponent $f$ are to be found among
these.

We show that $a''$ belongs to $\exp f\Leftrightarrow(v,\ f=1$.
Suppose $a''$ belongs to $\exp f'(:f'|f)$

\begin{description}

\item[(i)]
$(v,\ f)=1$ Suppose $(a'')^f\equiv1$ mod $p$ then $a''f\equiv 1$
mod $p$ but $a$ belongs to $\exp f$ and so $f|vf'$ therefore
$\|f'$ so $f=f'$.

\item[(ii)]
$(v,f)=d>1\\ (a^v)^\frac{f}{d}\equiv(a^f)^\frac{v}{d}\equiv1$ mod
$p$ since $a$ belongs to $\exp f$.

Thus $a''$ doesn't belong to $\exp f$ since $\frac{f}{d}<f.$ Hence
$\psi(f)=\phi(f)$.

We now prove

\end{description}

\item[(2)]
$\sum_{f|p-1}\psi(f)=p-1$

Every residue $\not\equiv 0$ mod $p$ belongs to exactly one
exponent $f$ and $a^f\equiv1$ mod $p\Leftrightarrow f|p-1$ for
$a^{p-1}\equiv1$ by Fermats theorem.

But $\sum_{f|p-1}\phi(f)=p-1$

So $\sum_{f|p-1}\left[\phi(f)-\psi(f)\right]=0,\
\left[\phi(f)-\psi(f)\right]\geq0$ by (1) therefore
$\phi(f)=\psi(f)$.

\end{description}

\item[Indices]
Suppose $g$ is a primitive root mod $p$, $p>2$.

Then $g^0,g^1,g^2,\ldots,g^{p-2}$ constitute an R.S.R. mod $p$.

For each $a$ satisfying $(a,\ p)=1\exists$ a unique integer $r$
such that $g^r\equiv a$ mod $p\ 0\leq r\leq p-2$

We write $r=md_ga$.

Then $a\equiv b$ mod $p\Leftrightarrow md_ga=md_gb$

$\left.\begin{array}{c}md_ga^n=nmd_ga\\md_gab=md_ga+md_gb\\
md_ga=md_gg;md_{g'}a\end{array}\right\}$ mod $p-1$

$md 1=0\\ md-1=\frac{p-1}{2}$, for $g^{p-1}\equiv0$ so
$\left(g^\frac{p-1}{2}-1\right)\left(g^\frac{p-1}{2}+1\right)\equiv0$
but $g^\frac{p-1}{2}\not\equiv1$ as $g$ is a primitive root so
$g^\frac{p-1}{2}\equiv -1$

\item[Example]\ \\

\begin{tabular}{cccc}
$p=13$&$g=2$&$N$&Index\\
&&1&0\\&&2&1\\&&4&2\\&&8&3\\&&3&4\\&&6&5\\
&&12&6\\&&11&7\\&&9&8\\&&5&9\\&&10&10\\&&7&11
\end{tabular}

\item[Example]
$\sum_{n=1}^{p-1}n^s\equiv\left\{\begin{array}{cl}0&\textrm{mod
$p$ if $s\not\equiv 0$ mod $p-1$}\\-1&\textrm{mod $p$ if
$s\equiv0$ mod $p-1$}\end{array}\right.$

\end{description}

\end{document}