Finite Mathematics

Robert S. Wilson

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

  1. a = qb + r
  2. q is the largest natural number such that qb < a
  3. 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.