## 8. The Division Algorithm and the Fundamental Theorem of
Arithmetic

**Theorem 8.1**:
**(The Division Algorithm)** Let a and b be natural numbers with b
not zero. Then there exist unique natural numbers q and r such that

- a = qb + r
- q is the largest natural number such that qb < a
- r < b.

**Definition 8.1**: Let a and b be two
natural numbers. We say that b **divides** a if there is a natural
number c such that

a = bc
If b divides a, we also say that b is a factor of a.

**Definition 8.2**: Let a and b be two
natural numbers. The Greatest Common Factor of a and b is the largest
natural number which divides both a and b.

**Theorem 8.2**: Any
two nonzero natural numbers will have a greatest common factor.

**Theorem 8.3**: Let
a and b be two nonzero natural numbers. The greatest common factor of
a and b is the smallest nonzero natural number that can be written as
a sum or difference of multiples of a and b.

**Definition 8.3**: Two nonzero natural
numbers are said to be relatively prime if their greatest common
factor is 1.

**Theorem 8.4**: If
a and b are relatively prime and a divides bc, then a divides c.

**Definition 8.4**: A natural number which
is greater than 1 is called a prime number if the only natural
numbers that divide it are itself and 1.

**Theorem 8.5: (The
Fundamental Theorem of Arithmetic) **

**Existence**: Every natural number greater than 1 is either
prime or can be written as a product of primes.

**Uniqueness**: Any factorization into a product of primes will
involve the same number of the same prime factors.