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
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
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.