<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

\begin{center}

THEORY OF NUMBERS

THE FUNDAMENTAL THEOREM OF ARITHMETIC

\end{center}

\begin{description}

\item[Theorem Euclids Algorithm]

Suppose $a&gt;0,\ b$ are integers. $\exists$ unique $q,\ r$ such that
$b=aq+r$ and $0\leq r&lt;a$.

\item[Proof]

\begin{description}

\item[(i)]

Existence

Choose the greatest value of $q$ such that $b-aq\leq0$ and write
$r=b-aq$ so $r&gt;0$. If $r\geq a$ then $b-a(q+1)\geq0$ which
contradicts the definition of $q$.

\item[(ii)]

Uniqueness

Suppose $\exists q',\ r'\ q'',\ r''$ with $q'&gt;q''$. Then $a\leq
a(q'-q'')=r''-r'&lt;a$ which gives us a contradiction.

\end{description}

\item[Definition]

A modulus of integers is a set $S$ of integers such that

\begin{description}

\item[(i)]

$S$ contains a non-zero element

\item[(ii)]

$m\in S,n\in S\Rightarrow m-n\in S$

\end{description}

\item[Theorem]

Every modulus of integers is equivalent to the set of all integer
multiples of some natural number.

\item[Proof]

Let $k$ be the least positive element in $S$. Let $T$ be the set
of all integral multiples of $k$.

\begin{description}

\item[(i)]

$T\subset S$

\begin{eqnarray*}
k\in S&amp;\Rightarrow&amp;k-k=0\in S\\ &amp;\Rightarrow&amp;0-k=-k\in S\\
&amp;\Rightarrow&amp;k-(-k)=2k\in S
\end{eqnarray*}

etc. (proof by induction).

\item[(ii)]

$S\subset T$

Let $x\in S$ By Euclids algorithm $\exists q,\ r$ such that
$x=qk+r\ 0\leq r\leq k,\ x\in S,\ qk\in S$ therefore $r\in S$
therefore $r=0$ therefore $x\in T$.

\end{description}

\item[Theorem]

Suppose $a,\ b$ are not both zero. $\exists$ a unique natural
number $d$ such that

\begin{description}

\item[(i)]

$d|a\ d|b$

\item[(ii)]

if $t|a$ and $t|b\Rightarrow t|d$

\item[(iii)]

$\exists x,\ y$ such that $d=ax+by$

\end{description}

$d$ is called the highest common factor (H.C.F) of $a,\ b$ denoted
by $(a,b)$.

\item[Proof]

\begin{description}

\item[(1)]

Existence

Consider the set of all numbers of the form $ax+by$. This set is a
modulus $S$ which has a generator $d$.

(iii) follows from the definition of $d,\ a\in S\ b\in S$
therefore (i) follows. (ii) follows from (iii)

\item[(2)]

Uniqueness

Suppose $d',\ d''$ satisfy (i) to (iii).

\begin{eqnarray*}
d'|a\textrm{ and }d'|b&amp;\Rightarrow&amp;d'|d''\\ d''|a\textrm{ and
}d''|b&amp;\Rightarrow&amp;d''|d'\\ &amp;\Rightarrow&amp;d'=d''
\end{eqnarray*}

\end{description}

\item[Corollary]
Suppose $a_1\ldots a_n$ are not all zero. $\exists$ a unique
$d=(a_1\ldots a_n)$ such that

\begin{description}

\item[(i)]

$d|a_1\ldots d|a_n$

\item[(ii)]

$t|a_1\ldots t|a_n\Rightarrow t|d$

\item[(iii)]

$\exists x_1\ldots x_n$ such that $d=a_1x_1+\ldots+a_nx_n$

\end{description}

The equation $a_1x_1+\ldots+\_nx_n=k$ is soluble $\Leftrightarrow
k|a$

\item[Theorem]

Suppose $p$ is prime and $p|ab$. Then either $p|a$ or $p|b$ or
both.

\item[Proof]

Suppose $p$ does not divide $a$. Then ($p,a$)=1. Hence $\exists
x,\ y$ such that $1=px+ay$ therefore $b=bpx+aby$ therefore $p|b$.

\item[Fundamental Theorem of arithmetic]

Every positive integer $\geq2$ is representable as a finite
product of positive primes, the representations being unique,
apart from order.

\item[Proof]

Suppose $n=p_1p_2\ldots p_r=q_1\ldots q_s$ is the smallest $n$
with two such representations. Then $p_1|q_j$ say. $p_q\ldots
p_r=q_1\ldots q_{j-1}q_{j+1}\ldots q_s$ this is smaller then $n$.
So the result follows.

\end{description}

\end{document}
</pre></body></html>