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.