## Number Theory

A number is **prime** if it has exactly two factors, 1 and the number itself. The first seven prime numbers are 2, 3, 5, 7, 11, 13, and 17. Teachers and students would do well to commit these numbers to memory. Notice that 1 is not a prime number because it has only one factor. A number greater than 1 that is not prime is said to be **composite.** Composite numbers have more than two factors. The number 6 is composite because its factors are 1, 2, 3, and 6. The Sieve of Eratosthenes is a method for finding all the primes less than or equal to a given number—for example, 100.

The prime factorization of a number is a product of primes that equals the number. The prime factorization of 6 is 2 × 3. The prime factorization of 18 is 2 × 3 × 3 = 2 × 3^{2}. The prime factorization of a prime number such as 5 is simply 5. A factor tree is often used to find prime factorizations. Although each whole number has a prime factorization, when a number is very large (several hundred digits), finding its prime factorization without using a computer is impracticable.

The counting numbers are 1, 2, 3, 4, 5, … . The fundamental theorem of arithmetic states that every counting number greater than 1 can be factored into primes in only one way. A different order, such as 6 = 2 × 3 and 6 = 3 × 2, does not count as a different way. Writing prime factorizations by listing primes in order makes it is easy to see that any number greater than 1 has only one prime factorization.

## Greatest Common Factor

The greatest common factor (GCF) of two numbers m and n is the greatest number that is a factor of both m and n. Since 1 is a factor of each number, all numbers have at least one common factor. One way to find the GCF is to write all the factors of m and then all the factors of n. The greatest factor common to both m and nis the GCF. Another way to find the GCF of m and n is to write the prime factorization of each number and then note the powers of primes that are common to both numbers. The GCF is the product of these common powers of primes.

Example:

Let m = 2 × 3^{4}× 7^{2}and n = 2^{2}× 3^{2}× 5^{3}× 7.

The powers of primes that are common are 2, 3^{2}, and 7.

So the GCF of m and n is 2 × 3^{2}× 7.

The GCF is also called the greatest common divisor (GCD) because when a number is a factor, it is also a divisor. The GCF is often used in simplifying fractions.

## Least Common Multiple

Recall that the multiples of a number, for example, 5, are the numbers that you get when you skip count, 5, 10, 15, 20, …. The least common multiple (LCM) of two numbers m and n is the least number that is a multiple of both m and n. Since m × n is a multiple of both m and n, there is at least one common multiple for any pair of numbers. One way to find the LCM is to use skip counting to write the multiples of m and the multiples of n up to m × n and then search for the least common multiple. Another method used to find the LCM of m and n is to write the prime factorization of each and note the highest power of each prime factor. The LCM is the product of these highest powers of primes.

Example:

Let m = 2 × 3^{4}× 7^{2}and n = 2^{2}× 3^{2}× 5^{3}× 7.

The highest power of primes are 2^{2}, 3^{4}, 5^{3}and 7^{2}.

So the LCM of m and n is 2^{2}× 3^{4}× 5^{3}× 7^{2}.

The least common multiple is used to find the least common denominator (LCD) when adding or subtracting fractions. Although the least common multiple of the denominators is the preferred common denominator when adding fractions, it is important that students realize that any common multiple of the denominators (including the product of the denominators) can be used as a common denominator.

**Teaching Model 3.3:** Prime Factorization