Contemporary Mathematics

# 3.1Prime and Composite Numbers

Contemporary Mathematics3.1 Prime and Composite Numbers

Figure 3.2 Computers are protected using encryption based on prime numbers. (credit: “Data Security” by Blogtrepreneur/Flickr, CC BY 2.0)

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:

• The counting numbers are referred to as the natural numbers. This set of numbers, ${1,2,3,4,…}{1,2,3,4,…}$, is denoted with the symbol $ℕℕ$.
• 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 ${…,−3,−2,−1,0,1,2,3,…}{…,−3,−2,−1,0,1,2,3,…}$. We denote the integers with the symbol ℤ.
• 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 $nn$ is divisible by $mm$, if $nn$ can be written as $mm$ times another integer. Equivalently, there is no remainder when $nn$ is divided by $mm$. 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.

### Example 3.1

#### Determining if a Number Divides Another Number

Determine if 36 is divisible by 4.

1.
Determine if 54 is divisible by 9.

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.

Divisor Rule
2 Last digit is even
3 Add the digits of the number together. If that sum is divisible by 3, then so is the original number
4 Look at only the last two digits. If this number is divisible by 4, so is the original number
5 Look at only the last digit. If it is a 5 or a 0, then the original number is divisible by 5
6 If the number passes the rule for divisibility by 2 and for 3, then the number is divisible by 6
9 Add the digits of the number together. If that number is divisible by 9, then so is the original number
10 Look at only the last digit. If it is a 0, then the original number is divisible by 10
12 If the number passes the rule for 3 and 4, the number is divisible by 12

### Example 3.2

#### Using Divisibility Rules

Using divisibility rules, determine if 245 is divisible by 5.

1.
Using divisibility rules, determine if 45,730 is divisible by 5.

### Example 3.3

#### Using Divisibility Rules

Using divisibility rules, determine if 25,983 is divisible by 9.

1.
Using divisibility rules, determine if 342,887 is divisible by 9.

### Example 3.4

#### Using Divisibility Rules

Can 298 coins be stacked into 6 stacks with an equal number of coins in each stack?

1.
Can 43,568 pieces of mail be separated into 6 bins with the same number of pieces of mail per bin?

### Example 3.5

#### Using Divisibility Rules

Using divisibility rules, determine if 4,259 is divisible by 10.

1.
Using divisibility rules, determine if 87,762 is divisible by 10.

### Example 3.6

#### Using Divisibility Rules

Using divisibility rules, determine if 936,276 is divisible by 4.

1.
Using divisibility rules, determine if 43,568 is divisible by 4.

### 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. Table 3.1 is a quick list of the prime numbers up to 50. There are 15 prime numbers less than 50.

 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Table 3.1 Prime Numbers Less than 50

### Example 3.7

#### Determining If a Number Is Prime or Composite

Determine if 2,117 is prime or composite.

1.
Determine if 1,429 is prime or composite.

### Example 3.8

#### Determining if a Number Is Prime or Composite

Determine if 423 is prime or composite.

1.
Determine if 859 is prime or composite.

### Example 3.9

#### Determining if a Number Is Prime or Composite

Determine if 1,034 is prime or composite

1.
Determine if 5,067,322 is prime or composite.

### Example 3.10

#### Determining if a Number Is Prime or Composite

Determine if 2,917 is prime or composite.

1.
Determine if 1,477 is prime.

### Who Knew?

#### ILLEGAL PRIMES

Large primes are a hot commodity. Using two very large primes (some have more than 22 million digits!) is necessary for secure encryption. Anyone who has a new prime that is large enough can use that prime to create a new encryption. Of course, whoever discovers a large prime could sell it to a security company. These primes are so useful for encryption, it is necessary to protect that intellectual property. In fact, at least one prime number was declared illegal.

### People in Mathematics

#### Sophie Germain

Figure 3.3 Sophie Germain (credit: “Sophie Germain at 14 years,” Illustration from histoire du socialisme, approx. 1880, Wikimedia Commons, public domain)

Born into a wealthy French family in 1776, Sophie Germain discovered and fell in love with mathematics by browsing her father’s books. Clandestine study, hard and tenacious work, and a mathematical mindset did not lead to college, however, as she was not allowed to attend. She did manage, through friends, to obtain problem sets and submit brilliant solutions under the name Monsieur LaBlanc. One of her great interests was number theory, which is the study of properties of integers. One of her theorems, titled “Sophie Germain’s Theorem,” partially solved one of the great mathematical mysteries, Fermat’s Last Theorem. From this she discovered what are now known as Sophie Germain Primes. A Sophie Germain Prime is a prime number that can be written in the form $2p+12p+1$, where $pp$ is a prime number. For instance, 23 is prime: $2(23)+1=472(23)+1=47$, which is prime, so 47 is a Sophie Germain Prime. It should be noted that $2p+12p+1$, where $pp$ is a prime number, may or may not be prime (check for $p=7p=7$!).

### 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 $3×243×24$. Notice that we could have factored the 72 differently, say as $72=6×1272=6×12$, or $72=2×3672=2×36$, or even as $72=3×4×672=3×4×6$.

Finding the prime factorization of a composite number means writing the number as the product of all of its prime factors. For example, $80=2×2×2×2×580=2×2×2×2×5$. 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 $80=24×580=24×5$. 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 $abab$, the number represented by $aa$ is the base, and the number represented by $bb$ 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.

### Example 3.11

#### Finding the Prime Factorization

Find the prime factorization of 140.

1.
Find the prime factorization of 90.

#### Factor Trees

A useful tool for helping with prime factorization is a factor tree. To create a factor tree for the natural number $nn$ (where $nn$ is not 1), perform the following steps:

Step 1: If $nn$ is prime, you're done. If $nn$ is composite, continue to the next step.

Step 2: Identify two divisors of $nn$, call them $aa$ and $bb$.

Step 3: Write the number $nn$ down, and draw two branches extending down (or to the right) of the number $nn$.

Step 4: Label the end of one branch $aa$, the other as $bb$. See Figure 3.4.

Figure 3.4

Step 5: If $aa$ and $bb$ 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 $aa$ or $bb$ are composite, repeat Steps 2 through 4 for $aa$ and $bb$.

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.

### Example 3.12

#### Finding the Prime Factorization

Find the prime factorization of 66.

1.
Find the prime factorization of 85.

### Example 3.13

#### Finding the Prime Factorization

Find the prime factorization of 135.

1.
Find the prime factorization of 280.

### Example 3.14

#### Identifying Prime Factors

How many different prime factors does 10,241 have?

1.
Find the number of different prime factors of 180.

### Tech Check

#### Using Wolfram Alpha to Find Prime Factorizations

The Wolfram Alpha website is a powerful resource available for free to use. It is designed using AI so that it understands natural language requests. For instance, typing the question “What is the prime factorization of 543,390?” gets a rather quick answer of $2×3×5×59×3072×3×5×59×307$. So, if you want to find the prime factorization of a number, you can simply ask Wolfram Alpha to find the prime factorization of the number.

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

 The divisors of 12 1, 2, 3, 4, 6, 12 The divisors of 18 1, 2, 3, 6, 9

It is easy to see that 6 is the largest value that appears in both lists.

### Example 3.15

#### Finding the Greatest Common Divisor Using Lists

Find the greatest common divisor of 1,400 and 250 by listing all divisors of each number.

1.
Find the greatest common divisor of 270 and 99 by listing all divisors of each number.

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.

### Example 3.16

#### Finding the Greatest Common Divisor Using Prime Factorization

Find the greatest common divisor of 1,400 and 250 by using their prime factorizations.

1.
Using prime factorization, determine the greatest common divisor of 36 and 128.

### Example 3.17

#### Finding the Greatest Common Divisor Using Prime Factorization

Find the greatest common divisor of 600 and 784 by using their prime factorizations.

1.
Using prime factorization, determine the greatest common divisor of 120 and 200.

### People in Mathematics

#### Srinivasa Ramanujan

Figure 3.10 Srinivasa Ramanujan (credit: Srinivasa Ramanujan, photo by Konrad Jacobs/Oberwolfach Photo Collection/public domain)

Ramanujan was born in southern India in 1887, during British rule. He was a self-taught mathematician, who, while in high school, began working through a two-volume text of mathematical theorems and results. His work included examination of the distribution of primes. He eventually came to the attention of British mathematician, G.H. Hardy. During one visit, Hardy mentioned to Ramanujan that his taxicab number was 1,729, remarking that 1,729 appeared to be a rather dull number. To which Ramanujan responded, “It is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways.”

### Tech Check

#### Using Desmos to Find the GCD

To find the GCD of a set of numbers in Desmos, type gcd(first_number,second_number…) and Desmos will display the GCD of the numbers, as the numbers are typed!

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

### Example 3.18

#### Calculating Floor Tile Size

Suppose you have a rectangular room that is 570 cm wide and 450 cm long. You wish to cover the floor of the room with square tiles. What’s the largest size square tile that can be used to cover this floor?

1.
You are designing a brick patio made of square bricks 5 cm thick, but you need to determine the width and length of those bricks. The patio will be 400 cm by 540 cm. What are the largest size square bricks that can be used so that you do not need to cut any bricks?

### Example 3.19

#### Organizing Books Per Shelf

Suppose you want to organize books onto shelves, and you want the shelves to hold the same number of books. Each shelf will only contain one genre of book. You have 24 sci-fi, 42 fantasy, and 30 horror books. How many books can go on each shelf?

1.
There are three gym classes. The number of students in the classes is 21, 35, and 28. What is the largest team size that can be formed if teams from every class must have the same number of students?

### 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 $aa$ divides the number $bb$, then $bb$ is a multiple of $aa$.

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.

### Example 3.20

#### Finding the Least Common Multiple Using Lists

Find the LCM of 24 and 90 by listing multiples and choosing the smallest common multiple.

1.
Use lists to find the LCM of 12 and 15.

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.

### Example 3.21

#### Finding the Least Common Multiple Using Prime Factorization

Use the prime factorizations of 24 and 90 to identify their LCM.

1.
Use prime factorization to find the LCM of 20 and 28.

### Example 3.22

#### Finding the Least Common Multiple Using Prime Factorization

Use the prime factorizations of 36, 66, and 250 to identify the LCM.

1.
Use the prime factorization method to find the LCM of 150, 240, and 462.

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.

### Example 3.23

#### Finding the Least Common Multiple Using Both Methods

Find the LCM of 20, 36, and 45 using lists and prime factorization.

1.
Find the LCM of 18, 24, and 40 using lists and prime factorization.

### Tech Check

#### Using Desmos to Find the LCM

To find the LCM of a set of numbers in Desmos, type lcm(first_number,second_number…) and Desmos will display the LCM of the numbers, as the numbers are typed!

### 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 Example 3.25, for instance). In each case, we may be looking to determine when two processes “line up.”

### Example 3.24

#### Determining Scheduling Overlap Using the Least Common Multiple

Two students, João, and Amelia, meet one day at an assisted living facility where they volunteer. João volunteers every 6 days. Amelia volunteers every 10 days. How many days will it be until they are both volunteering on the same day again?

1.
The sun, Venus, and Jupiter all line up on a given day. Venus orbits the sun once every 255 days. Jupiter orbits the sun every 4,330 days (we’ll ignore the decimal values of days for each orbit). How many days will it be until they line up again?

### Example 3.25

#### Determining the Minimum Height Using the LCM

A team-building exercise has teams build a house of cards as high as possible. However, the cards for different teams are of different sizes. Team 1 uses 10 cm × 10 cm cards, while Team 2 uses 8 cm × 8 cm cards. What is the minimum height when the two teams will be tied? Ignore the width of the cards.

1.
In an Internet giveaway, every 130th person who submits a survey receives \$250, and every 900th person receives a free cell phone. How many submissions must be received for the first person to receive both prizes?

### WORK IT OUT

Cicadas are known to have life cycles of 13 or 17 years, which are prime numbers. Why would a prime number life cycle be an evolutionary advantage? To figure this out, we have to explore how common multiples work with prime numbers.

Make a conjecture regarding the LCM of a prime number and another number. Test this conjecture with a few examples of your own making.

1.
Identify which of the following numbers are prime and which are composite.
31, 56, 213, 48, 701
2.
Find the prime factorization of 4,570.
3.
Find the greatest common divisor of 410 and 144.
4.
Find the least common multiple of 45 and 70.
5.
You want to fill gift bags for children in the after-school program where you volunteer. You have 30 crayons, 20 sticker sheets, and 70 bite-sized candies. If each gift bag must contain the same number of crayons, sticker sheets, and bite-sized candies, what is the maximum number of bags that can be filled?

### Section 3.1 Exercises

For the following exercises, use divisibility rules to determine if each of the following is divisible by 2.
1 .
24
2 .
37
3 .
1,345,321
For the following exercises, use divisibility rules to determine if each of the following is divisible by 3.
4 .
48
5 .
210
6 .
5,345,324
For the following exercises, use divisibility rules to determine if each of the following is divisible by 5.
7 .
130
8 .
237
9 .
1,345,321
For the following exercises, use divisibility rules to determine if each of the following is divisible by 9.
10 .
48
11 .
210
12 .
5,345,325
For the following exercises, use divisibility rules to determine if each of the following is divisible by 12.
13 .
48
14 .
210
15 .
5,355,324
16 .
Determine which of the following numbers are prime: {3, 27, 77, 131, 457}
17 .
Determine which of the following numbers are prime: {31, 97, 188, 389}
For the following exercises, find the prime factorization of the given number.
18 .
12
19 .
53
20 .
72
21 .
345
22 .
938
23 .
36,068
24 .
8,211,679
For the following exercises, find the greatest common divisor of the given set of numbers.
25 .
{45, 245}
26 .
{11, 24}
27 .
{56, 44}
28 .
{150, 600}
29 .
{1,746, 28,324}
30 .
{30, 40, 75}
31 .
{19, 45, 70}
32 .
{293, 7,298, 19,229}
33 .
{3,927,473, 82,709, 1,210,121}
34 .
Make a list of the common divisors of 12 and 18. What is the GCD of 12 and 18? Which of the other common divisors of 12 and 18 divide the GCD?
35 .
Make a list of the common divisors of 20 and 84. What is the GCD? Which of the other common divisors of 20 and 84 also divide the GCD?
36 .
Make a list of the common divisors of 120 and 88. What is the GCD? Which of the other common divisors of 120 and 88 also divide the GCD?
37 .
Based on the answers to 34, 35, and 36, make a conjecture about the GCD of two numbers, and the other common divisors of those numbers.
38 .
Rebecca wants to cut two lengths of board into equal length pieces, with no leftover piece. The two boards are 230 cm long and 370 cm long. What is the longest length that Rebecca can cut from these boards so that all the cut boards are the same length?
39 .
Yasmin is playing with her younger brother, Cameron. They are grouping Skittles by color. They have 14 green, 10 yellow, and 8 purple Skittles. Each group must have the same number of green, the same number of yellow, and the same number of purple Skittles. What’s the maximum number of piles that Sophia can build with Cameron?
40 .
Gathii is creating a tile backsplash for his kitchen. He wants to use square tiles to cover a 330 cm × 12 cm area. What is the largest size square tile he can use to create this backsplash?
41 .
Deiji is designing a contest where teams will be given the same number of toothpicks, 5 oz. paper cups, and 2 cm length pieces of string. She has 420 pieces of string, 300 paper cups, and 1,610 toothpicks. What is the maximum number of teams she can have so that every team gets an equal number of pieces of string, paper cups, and toothpicks?
For the following exercises, find the least common multiple of the given set of numbers.
42 .
{30, 40}
43 .
{11, 24}
44 .
{14, 45}
45 .
{200, 450}
46 .
{38,077, 9,088,687}
47 .
{36, 42, 70}
48 .
{7, 13, 36}
49 .
{4,450,864, 339,889, 157,339}
50 .
Benjamin and Mia both work at the Grease Fire diner, a local eatery. Benjamin has every 4th day off, and Mia has every 6th day off. How many days pass until they have another day off together?
51 .
A lunar month is 30 days (rounding off). A new lunar month begins on a Saturday. How many days is it until a lunar month begins on a Saturday again?
52 .
Isabella is creating a collage for a project and wants a horizontal cut in the collage. The cut will be made by using purple strips of cloth that are 28 mm long, and yellow strips of paper that are 36 mm long. What is the minimum length of the cut can she make using strips with those lengths?
53 .
Asteroids are objects that orbit the sun. The smallest distance that an asteroid gets to the sun during its orbit is called the perihelion. Asteroids also have orbital periods, or the time it takes to go around the sun exactly one time. The asteroid Ceres has an orbital period (number of days to circle the sun) of 1,680 days. The asteroid Hygiea has an orbital period of 2,031 days. Suppose they are at their perihelion on the same day. How many days will it be before Ceres and Hygiea are at their perihelion on the same day again?
Order a print copy

As an Amazon Associate we earn from qualifying purchases.