3.1 Prime and Composite Numbers

A laptop screen shows a lock symbol. — **Figure 3.2** Computers are protected using encryption based on prime numbers.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:

Apply divisibility rules.
Define and identify numbers that are prime or composite.
Find the prime factorization of composite numbers.
Find the greatest common divisor.
Use the greatest common divisor to solve application problems.
Find the least common multiple.
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, and so on }$ , 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 ${\dots, - 3, - 2, - 1, 0, 1, 2, 3, \dots}$ . 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 $n$ is divisible by $m$ , if $n$ can be written as $m$ times another integer. Equivalently, there is no remainder when $n$ is divided by $m$ . 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.

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

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.

**Table 3.1**
2	3	5	7	11
13	17	19	23	29
31	37	41	43	47

Example 7 Determining If a Number Is Prime or Composite

Determine if 2,117 is prime or composite.

The square root of 2,117 is 46.0 (rounded to one decimal place). So, we need to check if 2,117 is divisible by any prime up to 46.

Step 1: First we’ll use the rules of divisibility we learned earlier:

We can tell 2,117 is not divisible by 2, as the last digit isn't even.
2,117 is not divisible by 5 (the last digit isn't 0 or 5).
Add the digits of 2,117 to get 11, which is not divisible by 3. So, 2,117 is also not divisible by 3.

Step 2: Now we repeat the process for all the primes up to 46.

Using a calculator, we find that 2,117 divided by the prime numbers 7, 11, 13, 17, 19, and 23 results in a remainder, a decimal part. So, we know that 2,117 is not divisible by these prime numbers. (You should check these results yourself.)

Moving on, we check the next prime: 29. Using the calculator to divide 2,117 by 29 results in 73. Since there is no decimal part, 2,117 is divisible by 29.

This means that 2,117 is not a prime number, but rather, a composite number. Writing 2,117 as the product of 29 and another natural number, $2,117 = 29 \times 73$ .

Example 10 Determining if a Number Is Prime or Composite

Determine if 2,917 is prime or composite.

The square root of 2,917 is 50.01 (rounded to two decimal places). So, we need to check if 2,917 is divisible by any prime up to 50.

Step 1: Check 2. We can tell 2,917 is not divisible by 2, as the last digit isn't even.

Step 2: Check 5. It is it divisible by 5 (the last digit isn't 0 or 5).

Step 3: Check 3. Using the divisibility rule for 3, we take the sum of the digits of 2,917, which is 19. Since 19 is not divisible by 3, neither is 2,917.

Step 4: Check the rest of the primes up to 50 using a calculator. When 2,917 is divided by every prime number up to 50, the result has a decimal part.

Since no prime up to 50 divides 2,917, it is a prime number.

People in Mathematics

Sophie Germain

Figure 3.3 Sophie GermainSophie 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 $2 p plus 1$ , where $p$ is a prime number. For instance, 23 is prime: $2 (23) + 1 = 47$ , which is prime, so 47 is a Sophie Germain Prime. It should be noted that $2 p plus 1$ , where $p$ is a prime number, may or may not be prime (check for $p equals 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 times 24$ . Notice that we could have factored the 72 differently, say as $72 = 6 \times 12$ , or $72 = 2 \times 36$ , or even as $72 = 3 \times 4 \times 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 \times 2 \times 2 \times 2 \times 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 = 2^{4} \times 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 $a^{b}$ , the number represented by $a$ is the base, and the number represented by $b$ 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 11 Finding the Prime Factorization

Find the prime factorization of 140.

Step 1: Identify a prime number that divides 140. Since 140 is even (the last digit is even), 2 divides 140. We then factor the 2 out of the 140, giving us $140 = 2 \times 70$ .

Step 2: With the other factor, 70, find a prime factor of 70. Since 70 is also even, 2 divides 70. We factor the 2 out of the 70 and the factorization is now $140 = 2 \times 2 \times 35 = 2^{2} \times 35$ .

Notice that we expressed the two factors of 2 as $2 squared$ .

Step 3: Look to the remaining factor, 35. The last digit of 35 is 5, so 5 is a factor of 35. We factor the 5 out of the 35. The factorization is now $140 = 2^{2} \times 5 \times 7$ .

Step 4: Look to the remaining factor, 7. Since 7 is prime, the process is complete.

The prime factorization of 140 is $2^{2} \times 5 \times 7$ .

Factor Trees

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

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

Step 2: Identify two divisors of $n$ , call them $a$ and $b$ .

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

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

A tree diagram shows two branches extending down from a node labeled 66 to 2 and 33. — **Figure 3.4**

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

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 14 Identifying Prime Factors

How many different prime factors does 10,241 have?

To know how many different prime factors 10,241 has, we need the prime factorization of 10,241.

Step 1: Use divisibility rules, to see that the number 10,241 is not divisible by 2 or by 3 (the sum of the digits is 8), or by 5. However, it is divisible by 7.

Step 2: After factoring the 7, the factorization is $10,241 = 7 \times 1463$ ; 1,463 is also divisible by 7.

Step 3: After factoring the 7, the factorization is $10,241 = 7 \times 7 \times 209 = 7^{2} \times 209$ . The number 209 is not divisible by 7.

Step 4: Check the next prime number: 11; 11 does divide 1,463.

Step 5: After factoring the 11, the factorization is $10,241 = 7^{2} \times 11 \times 19$ .

Since 19 is prime, the prime factorization of 10,241 is complete. We see that 10,241 has three different prime factors: 7, 11, and 19.

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.

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 16 Finding the Greatest Common Divisor Using Prime Factorization

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

Step 1: Find the prime factorizations of the numbers.

The prime factorization of 1,400 is $2^{3} \times 5^{2} \times 7$ .

The prime factorization of 250 is $250 = 2 \times 5^{3}$ .

Step 2: Identify the prime factors that appear in every number’s prime factorization.

The common prime factors are 2 and 5.

Step 3: Identify the smallest exponent of each prime identified in Step 2 in the prime factorizations.

The exponent of common prime factor 2 in the prime factorization of 1,400 is 3, and in the prime factorization of 250 is 1. The smallest of those exponents is 1.

The exponent of the common prime factor 5 in the prime factorization of 1,400 is 2 and is in the prime factorization of 250 is 3. The smallest of these exponents is 2.

Step 4: Multiply the prime factors identified in Step 2 raised to the powers identified in Step 3.

This gives $2^{1} \times 5^{2} = 50$ . The greatest common divisor of 1,400 and 250 is $2 \times 5^{2} = 50$ .

Notice that the answer matches the one we found in Example 15.

Example 17 Finding the Greatest Common Divisor Using Prime Factorization

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

Step 1: Find the prime factorizations of the numbers.

The prime factorization of 600 is $2^{3} \times 3 \times 5^{2}$ .

The prime factorization of 784 is $2^{4} \times 7^{2}$ .

Step 2: Identify the prime factors that appear in every number’s prime factorization.

There is only one common prime factor, 2.

Step 3: Identify the smallest exponent of each prime from identified in Step 2 in the prime factorizations.

The exponent of 2 in the prime factorization of 600 is 3. The exponent of 2 in the prime factorization of 784 is 4. So, the smallest exponent of 2 is 3.

Step 4: Multiply the prime factors identified in Step 2 raised to the powers identified in Step 3.

This gives $2 cubed equals 8$ . The greatest common divisor of 600 and 784 is 8.

People in Mathematics

Srinivasa Ramanujan

Figure 3.10 Srinivasa RamanujanSrinivasa 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.”

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

Using squares means that the length and width of the tiles are equal. To ensure we are using full tiles, the side length of the square tiles must divide the length of the room and the width of the room. Since we want the largest square tiles, we need the GCD of the width and length of the room or the GCD of 570 and 450.

Step 1: Find the prime factorizations of the numbers.

The prime factorization of 570 is $2 \times 3 \times 5 \times 19$ .

The prime factorization of 450 is $2 \times 3^{2} \times 5^{2}$ .

Step 2: Identify the prime factors that appear in every number’s prime factorization.

The common prime factors are 2, 3, and 5.

Step 3: Identify the smallest exponent of each prime identified in Step 2 in the prime factorizations.

The exponents of 2 in the prime factorizations of 570 and 450 are 1 and 1. So the smallest exponent for 2 is 1.

The exponents of 3 in the prime factorizations of 570 and 450 are 1 and 2, so the smallest exponent for 3 is 1.

The exponents of 5 in the prime factorizations of 570 and 450 are 1 and 2, so the smallest exponent for 5 is 1.

Step 4: Multiply the prime factors identified in Step 2 raised to the powers identified in Step 3.

This gives $2^{1} \times 3^{1} \times 5^{1} = 30$ . The GCD of 450 and 570 is 30, so the largest size square tile that can be used to cover the floor is 30 cm by 30 cm.

Example 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?

Since we want shelves that hold an equal number of books, and a shelf can only hold one genre of book, we need a number that will equally divide 24, 42, and 30. So, we need the GCD of the number of books of each genre or the GCD of 24, 42, and 30.

Step 1: Find the prime factorizations of the numbers.

The prime factorization of 24 is $2 cubed times 3$ .

The prime factorization of 42 is $2 \times 3 \times 7$ .

The prime factorization of 30 is $2 \times 3 \times 5$ .

Step 2: Identify the prime factors that appear in every number’s prime factorization.

The common prime factors are 2 and 3.

Step 3: Identify the smallest exponent of each prime identified in Step 2 in the prime factorizations.

The smallest exponent of 2 and 3 in the factorizations is 1.

Step 4: Multiply the prime factors identified in Step 2 raised to the powers identified in Step 3.

This gives $2^{1} \times 3^{1} = 6$ . The GCD of 24, 42, and 30 is 6, so the largest number of books that can go on a shelf is 6.

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

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.

Example 21 Finding the Least Common Multiple Using Prime Factorization

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

Step 1: Find the prime factorization of each number.

$24 = 2^{3} \times 3$

$90 = 2 \times 3^{2} \times 5$

Step 2: Identify each prime that is present in any of the prime factorizations.

The prime numbers present in the prime factorizations are 2, 3, and 5.

Step 3: Identify the largest exponent of each prime identified in Step 2 in the prime factorizations.

Prime	2	3	5
Largest exponent	3	2	1

Step 4: Compute the LCM by multiplying the prime factors identified in Step 2 raised to the powers identified in Step 3.

The LCM for 24 and 90 is $2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^{3} \times 3^{2} \times 5^{1} = 360$ .

Example 22 Finding the Least Common Multiple Using Prime Factorization

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

Step 1: Find the prime factorization of each number.

$36 = 2^{2} \times 3^{2}$

$66 = 2 \times 3 \times 11$

$250 = 2 \times 5^{3}$

Step 2: Identify each prime that is present in any of the prime factorizations.

The prime numbers present in the prime factorizations are 2, 3, 5, and 11.

Step 3: Identify the largest exponent of each prime identified in Step 2 in the prime factorizations.

Prime	2	3	5	11
Largest exponent	2	2	3	1

Step 4: Compute the LCM by multiplying the prime factors identified in Step 2 raised to the powers identified in Step 3.

The LCM for 36, 66, and 250 is $2 \times 2 \times 3 \times 3 \times 5 \times 5 \times 5 \times 11 = 2^{2} \times 3^{2} \times 5^{3} \times 11^{1} = 49,500$ .

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 23 Finding the Least Common Multiple Using Both Methods

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

Step 1: Use listing. List the multiples:

20	20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220
36	36, 72, 108, 144, 180, 216, 252, 288, 324, 360
45	45, 90, 135, 180, 225, 270, 315, 360, 405, 450, 495, 540

The smallest value that appears on all the lists is 180, so 180 is the LCM of 20, 36, and 45.

Step 2: Find the prime factorization of each number.

$20 = 2^{2} \times 5$

$36 = 2^{2} \times 3^{2}$

$45 = 3^{2} \times 5$

Step 3: Identify each prime that is present in any of the prime factorizations.

The prime numbers present in the prime factorizations are 2, 3, 5.

Step 4: Identify the largest exponent of each prime identified in Step 3 in the prime factorizations.

Prime	2	3	5
Largest exponent	2	2	1

Step 5: Compute the LCM by multiplying the prime factors identified in Step 3 raised to the powers identified in Step 4.

The LCM for 20, 36, and 45 is $2^{2} \times 3^{2} \times 5^{1} = 180$ .

Both listing and prime factorization produced the same result: the LCM is 180.

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

Example 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?

If we list the days that each student will volunteer, it becomes clear that we could solve this problem using the LCM of 6 and 10.

João will be at the assisted living facility 6, 12, 18, 24, 30, 36, 42, and 48 days later.

Amelia will be at the assisted living facility 10, 20, 30, 40, 50, and 60 days later.

The smallest number appearing on both lists is 30. João and Amelia will once more be volunteering together 30 days later.

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

This is an example where we want to put together objects with different sizes. We want to know the minimum height when they are tied, or when the houses of cards line up the first time. The heights of the towers built using the 10 cm × 10 cm cards will be 10, 20, 30, 40, 50, and 60 cm tall. When the 8 cm × 8 cm cards are used, the tower will be 8, 16, 24, 32, 40, 48, and 56 cm tall. The smallest number appearing on both lists is 40. The first time they are tied is when the two towers are 40 cm tall.

Key Terms

natural numbers
factor of a number
multiple of a number
prime number
composite number
prime factorization
greatest common divisor (GCD)
least common multiple (LCM)

Key Concepts

The natural numbers can be categorized as 1, prime numbers, and composite numbers.
Prime numbers have as their only factors 1 and themselves.
Composite numbers have at least three distinct factors.
Composite numbers can be written in their prime factorization form, which is found by repeatedly factoring prime factors from the number.
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.
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.
There are various ways that the GCD and LCM are applied.

Videos

Adapted from Contemporary Mathematics by OpenStax (openstax.org), licensed under CC BY-NC-SA 4.0. Changes were made. License: CC-BY-NC-SA-4.0.