# Real Number Systems and Number Theory

## Prime and Composite Numbers

After completing this section, you should be able to:
1. Apply divisibility rules.
2. Define and identify numbers that are prime or composite.
3. Find the prime factorization of composite numbers.
4. Find the greatest common divisor.
5. Use the greatest common divisor to solve application problems.
6. Find the least common multiple.
7. Use the least common multiple to solve application problems.
Encryption, which is needed for the secure exchange of information (i.e., online banking or shopping) is based on prime numbers. Encryption uses a composite number that is the product of two very large prime numbers. To break the encryption, the two primes that were used to form the composite number need to be determined. If the two prime numbers used are sufficiently large, even the fastest computer cannot determine those two prime numbers in a reasonable amount of time. It would take a computer 300 trillion years to crack the current encryption standard.

### Applying Divisibility Rules

 
Before we begin our investigation of divisibility, we need to know some facts about important sets of numbers:
1. The counting numbers are referred to as the natural numbers. This set of numbers, , is denoted with the symbol .
2. Another important set of numbers is the integers. The integers are the natural numbers, along with 0, and the negatives of the natural numbers. This set is often written as . We denote the integers with the symbol ℤ.
3. Notice that ℕ is a proper subset of ℤ, or, ℕ ⊂ ℤ. All the ideas of this section apply to the natural numbers, while only some apply to all the integers.
Divisibility is when the integer  is divisible by , if  can be written as  times another integer. Equivalently, there is no remainder when  is divided by . There are many occasions when separating items into equal groups comes into play to ensure an equal distribution of whole items. For example, Francis, a preschool art teacher, has 15 students in one class. Francis has 225 sheets of construction paper and wants to provide each student with an equal number of pieces. To know if he will use all the construction paper, Francis is really asking if 225 can be evenly divided into 15 groups.
You can quickly check if a number is divisible by 2, 3, 4, 5, 6, 9, 10, and 12. Each has an easy-to-identify feature, or rule, that indicates the divisibility by those numbers, as shown in the following table.

### Prime and Composite Numbers

Sometimes, a natural number has only two unique divisors, 1 and itself. For instance, 7 and 19 are prime. In other words, there is no way to divide a prime number into groups with an equal number of things, unless there is only one group, or those groups have one item per group. Other natural numbers have more than two unique divisors, such as 4, or 26. These numbers are called composite. The number 1 is special; it is neither prime nor composite.
To determine if a number is prime or composite, you have to determine if the number has any divisors other than 1 and itself. The divisibility rules are useful here, and can quickly show you if a number has a divisor on that list.
However, if none of those divide the number, you still have to check all other possible prime divisors. What are the prime numbers that are possibly divisors of the number you are checking? You need only check the prime numbers up to the square root of the number in question. For instance, if you want to know if 2,117 is prime, you need to determine if any primes up to the square root of 2,117 (which is 46.0 when rounded to one decimal place) divide 2,117. If any of those primes are divisors of the number in question, then the number is composite. If none of those primes work, then the number is itself prime.
We can check divisibility with whatever tool we wish. Divisibility rules are quick for some prime divisors (2 and 5 come to mind) but aren't quick for other values (like 11). In place of divisibility rules, we could just use a calculator. If the prime number divides the number evenly (that is, there is no decimal or fractional part), then the number is divisible by that prime.  is a quick list of the prime numbers up to 50. There are 15 prime numbers less than 50.

### Finding the Prime Factorization of Composite Numbers

Before we can start with prime factorization, let’s remind ourselves what it means to factor a number. We factor a number by identifying two (or more) numbers that, when multiplied, result in the original number. For instance, 3 and 24, when multiplied, give 72. So, 72 can be factored into . Notice that we could have factored the 72 differently, say as , or , or even as .
Finding the prime factorization of a composite number means writing the number as the product of all of its prime factors. For example, . Notice that all the numbers being multiplied on the right-hand side are prime numbers. Sometimes prime numbers repeat themselves in the factorization. When prime factors do repeat, we may write the prime factorization using exponents, as in . In that equation, the 2 is raised to the 4th power. The 4 is the exponent, and the 2 is the base. More generally, in the exponent notation , the number represented by  is the base, and the number represented by  is the exponent.
One has to wonder if finding the prime factorization could result in different factorizations. The Fundamental Theorem of Arithmetic tells us that there is only one prime factorization for a given natural number.

### Fundamental Theorem of Arithmetic

Every natural number, other than 1, can be expressed in exactly one way, apart from the arrangement, as a product of primes.
The process of finding the prime factorization of a number is iterative, which means we do a step, then repeat it until we cannot do the step any longer. The step we use is to identify one prime factor of the number, then write the number as the prime factor times another factor. We repeat this step on the other, newly found, factor. This step is repeated until no more primes can be factored from the remaining factor. This is easier to see and explain with an example.

### Factor Trees

A useful tool for helping with prime factorization is a factor tree. To create a factor tree for the natural number  (where  is not 1), perform the following steps:
Step 1: If  is prime, you're done. If  is composite, continue to the next step.
Step 2: Identify two divisors of , call them  and .
Step 3: Write the number  down, and draw two branches extending down (or to the right) of the number .
Step 4: Label the end of one branch , the other as . See .
Step 5: If  and  are prime, the tree is complete. When a number at this step is a prime number, we refer to it as a leaf of the tree diagram.
Step 6: If either  or  are composite, repeat Steps 2 through 4 for  and .
Step 7: The process stops when the leaves are all prime.
Step 8: The prime factorization is then the product of all the leaves.
This is best seen in an example.

### Finding the Greatest Common Divisor

Two numbers often have more than one divisor in common (all pairs of natural numbers have the common divisor 1). When listing the common divisors, it’s often the case that the largest is of interest. This divisor is called the greatest common divisor and is denoted GCD. It is also sometimes referred to as the greatest common factor (GCF).
For instance, 6 is the greatest common divisor of 12 and 18. We can see this by listing all the divisors of each number and, by inspection, select the largest value that shows up in each list.
It is easy to see that 6 is the largest value that appears in both lists.
Listing all the divisors of the numbers in the set will always work, but for some relatively small numbers, the set of all divisors can become pretty big, and finding them all can be a chore. Another approach to finding the greatest common divisor is to use the prime factorization of the numbers. To do so, use the following steps:
Step 1: Find the prime factorization of the numbers.
Step 2: Identify the prime factors that appear in every number’s prime factorization. These are called the common prime factors.
Step 3: Identify the smallest exponent of each prime factor identified in Step 2 in the prime factorizations.
Step 4: Multiply the prime factors identified in Step 2 raised to the powers identified in Step 3. The result is the greatest common divisor.

### Applications of the Greatest Common Divisor

The greatest common divisor has uses that are related to other mathematics (reducing fractions) but also in everyday applications. We’ll look at two such applications, which have very similar underlying structures. In each case, something must divide the groups or measurements equally.

### Finding the Least Common Multiple

The flip side to a divisor of a number is a multiple of a number. For example, 5 is a divisor of 45 and so 45 is a multiple of 5. More generally, if the number  divides the number , then  is a multiple of .
This drives the idea of the least common multiple of a set of numbers. A common multiple of a set of numbers is a multiple of each of those numbers. For instance, 45 is a common multiple of 9 and 5, because 45 is a multiple of 9 (9 divides 45) and 45 is also a multiple of 5 (5 divides 45). The least common multiple (LCM) of a set of number is the smallest positive common multiple of that set of numbers.
There are (at least) three ways to find the LCM of a set of numbers, and we will explore two of them. One way is to create a list of multiples of each number in the set, and then identify the smallest multiple that appears in those lists.
The second method we can use is to find the prime factorizations of the number in the set to build the LCM of the numbers based on the prime divisors of the numbers. The LCM can be built from the prime factorization of the numbers in the set in a similar way as when finding the greatest common divisor. Here are the steps for using the prime factorization process for finding the LCM.
Step 1: Find the prime factorization of each number.
Step 2: Identify each prime that is present in any of the prime factorizations.
Step 3: Identify the largest exponent of each prime identified in Step 2 in the prime factorizations.
Step 4:. Multiply the prime factors identified in Step 2 raised to the powers identified in Step 3.
Using lists for three or more numbers, particularly larger numbers, could take quite a bit of time. Frequently, as in this example, the prime factorization process is much quicker. In practice, you can use either listing or prime factorization to find the LCM.

### Applications of the Least Common Multiple

Some applications of LCM involve events that repeat at fixed intervals, such as visits to a location. Other applications involve getting things to be of equal magnitude when using parts that are different sizes (see , for instance). In each case, we may be looking to determine when two processes “line up.”

### Check Your Understanding


### Key Terms

1. natural numbers
2. factor of a number
3. multiple of a number
4. prime number
5. composite number
6. prime factorization
7. greatest common divisor (GCD)
8. least common multiple (LCM)

### Key Concepts

1. The natural numbers can be categorized as 1, prime numbers, and composite numbers.
2. Prime numbers have as their only factors 1 and themselves.
3. Composite numbers have at least three distinct factors.
4. Composite numbers can be written in their prime factorization form, which is found by repeatedly factoring prime factors from the number.
5. The greatest common divisor (GCD) of a set of numbers is the largest integer that divides all of the numbers in the set. The prime factorizations of the numbers can be used to identify the greatest common divisor.
6. The least common multiple (LCM) of a set of numbers is the smallest integer that is divisible by all of the numbers in the set. The prime factorizations of the numbers can be used to identify the least common multiple.
7. There are various ways that the GCD and LCM are applied.

### Videos

1. Divisibility Rules
2. Illegal Prime Number
3. Using a Factor Tree to Find the Prime Factorization
4. Finding the Prime Factorization of 168
5. Using Desmos to find the GCD
6. Applying the GCD
7. Finding the LCM
8. Using Desmos to find the LCM
9. Application of LCM