In this lecture, we study some basic number theory as it is needed to study group theory.

Let $\mathbb{Z}$ denote the set of integers. $\mathbb{Z}$ satisfies *well-ordering principle*, namely any non-empty set of nonnegative integers has a smallest member.

One of the most fundamental theorems regarding numbers is *Euclid’s Algorithm*. Although we will not discuss its proof, it can be proved using well-ordering principle.

*Theorem*. [Euclid’s Algorithm] If $m$ and $n$ are integers with $n>0$, then $\exists$ integers $q$ and $r$ with $0\leq r<n$ such that $m=qn+r$.

Euclid’s algorithm hints us how we can define the notion that one integer divides another.

*Definition*. Given $m\ne 0, n\in\mathbb{Z}$, we say $m$ divides $n$ and write $m|n$ if $n=cm$ for some $c\in\mathbb{Z}$.

*Examples*. $2|14$, $(-7)|14$, $4|(-16)$.

If $m|n$, we call $m$ a *divisor* or a *factor* of $n$, and $n$ a multiple of $m$. To indicate $m$ is not a divisor of $n$, we write $m\not|n$. For example, $3\not|5$.

*Lemma*. The following properties hold.

(a) $1|n$ $\forall n$.

(b) If $m\ne 0$ then $m|0$.

(c) If $m|n$ and $n|q$, then $m|q$.

(d) If $m|n$ and $m|q$ then $m|(\mu n+\nu q)$ $\forall \mu,\nu$.

(e) If $m|1$ then $m=\pm 1$.

(f) If $m|n$ and $n|m$ then $m=\pm n$.

*Definition*. Given $a,b$ (not both 0), their *greatest common divisor* (in short gcd) $c$ is defined by the following properties:

(a) $c>0$

(b) $c|a$ and $c|b$

(c) If $d|a$ and $d|b$ then $d|c$.

If $c$ is the gcd of $a$ and $b$, we write $c=(a,b)$.

$(24,9)=3$. Note that the gcd 3 can be written in terms of 24 and 9 as $3\cdot 9+1\cdot (-24)$ or $(-5)9+2\cdot 24$. In general, we have the following theorem holds.

*Theorem*. If $a,b$ are not both 0, their gcd exists uniquely. Moreover, $\exists m,n\in\mathbb{Z}$ s.t. $c=ma+nb$.

Now let us talk about how to find the gcd of two positive numbers $a$ and $b$. W.L.O.G. (Without Loss Of Generality), we may assume that $b<a$. Then by Euclid’s algorithm we have

$$a=bq+r,\ \mbox{where}\ 0\leq r<b.$$

Let $c=(a,b)$. Then $c|r$, so $c$ is a common divisor of $b$ and $r$. If $d$ is a common divisor of $b$ and $r$, it is also a common divisor of $a$ and $b$. This implies that $d\leq c$ and so $c=(b,r)$. Finding $(b,r)$ is of course easier because one of the numbers is smaller than before.

*Example*. [Finding GCD]

$$

\begin{aligned}

(100,28)&=(28,16)\ &(100&=28\cdot 3+16)\\

&=(16,12)\ &(28&=16\cdot 1+12)\\

&=(12,4)\ &(16&=12\cdot 1+14)\\

&=4.

\end{aligned}

$$

By working backward, we can also find integers $m$ and $n$ such that

$$4=m\cdot 100+n\cdot 28.$$

\begin{align*}

4&=16+12(-1)\\

&=16+(-1)[28+(-1)16]\\

&=(-1)28+2\cdot 16\\

&=(-1)28+2[100+(-3)28]\\

&=2\cdot 100+(-7)28.

\end{align*}

Therefore, $m=2$ and $n=-7$.

*Definition*. We say that $a$ and $b$ are *relatively prime* if $(a,b)=1$.

*Theorem*. The integers $a$ and $b$ are relatively prime if and only if $1=ma+nb$ for some $m$ and $n$.

*Theorem*. If $(a,b)=1$ and $a|bc$ then $a|c$.

*Theorem*. If $b$ and $c$ are both relatively prime to $a$, then $bc$ is also relatively prime to $a$.

*Definition*. A *prime number*, or shortly *prime*, is an integer $p>1$ such that $\forall a\in\mathbb{Z}$, either $p|a$ or $(p,a)=1$.

Suppose that $p$ is a prime as defined above and $p=ab$, where $1\leq a<p$. Then $p\not|a$ since $a<p$, so $(p,a)=1$. This implies that $p|b$. On the other hand, $b|p(=ab)$ and hence $p=b$ and $a=1$. So, the above definition coincides with the definition of a prime we are familiar with.

*Theorem*. If $p$ is a prime and $p|a_1a_2\cdots a_n$, then $p|a_i$ for some $i$ with $1\leq i\leq n$.

*Proof*. If $p|a_1$, we are done. If not, $(p,a_1)=1$ and so $p|a_2a_3\cdots a_n$. Continuing this, we see that $p|a_i$ for some $i$.

Regarding primes, we have the following theorems.

*Theorem*. If $n>1$, then either $n$ is a prime or the product of primes.

*Theorem*. [Unique Factorization Theorem] Given $n>1$, there is a unique way to write $n$ in the form $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where $p_1<p_2<\cdots<p_k$ are primes and the exponents $a_1,\cdots,a_k$ are all positive.

*Theorem*. [Euclid] There is an infinite number of primes.