Prime Numbers and Prime Factorization
In gym class, Coach Rivera wants to line up $13$ students in equal rows for a stretching drill. It doesn't work: the only choices are $1$ row of $13$ students or $13$ rows of $1$. With $12$ students it's easy: $2 \times 6$, $3 \times 4$, $1 \times 12$... Why is $13$ so stubborn and $12$ so flexible? The answer is in their factors.
Prime and Composite Numbers
A factor of a number is a whole number that divides it evenly (with no remainder). The factors of $12$ are $1, 2, 3, 4, 6$ and $12$. The factors of $13$ are only $1$ and $13$.
In PE class, the teacher wants to organize the $13$ students into perfect rows and columns to do an exercise (for example, $2$ rows of $6$ people). a) Why can't he do…
In PE class, the teacher wants to organize the $13$ students into perfect rows and columns to do an exercise (for example, $2$ rows of $6$ people).
- a) Why can't he do this with $13$ students in any way other than a single row of $13$?
- b) What type of number is $13$ according to its factors?
Look at the following numbers and identify which ones are composite, justifying your answer (indicating at least three factors for each one): $15, 17, 21, 23, 27$
Look at the following numbers and identify which ones are composite, justifying your answer (indicating at least three factors for each one):
$15, 17, 21, 23, 27$
A video game programmer wants to create a "final boss" whose strength level is the product of the first three different prime numbers. What strength level will the…
A video game programmer wants to create a "final boss" whose strength level is the product of the first three different prime numbers. What strength level will the monster have?
The Sieve of Eratosthenes
More than 2,000 years ago, the Greek mathematician Eratosthenes invented a "filter" that finds every prime up to any number you choose. You cross out the multiples of each prime you find, and whatever survives is prime.
The sieve as an algorithm
An algorithm is a precise list of steps. Here is the sieve for the numbers up to $30$:
-
Write the numbers from $2$ to $30$. Leave out $1$ because it is not prime.
-
Circle the smallest number that is not circled or crossed out yet.
-
Cross out all the multiples of that number that are bigger than it. Do not cross out the circled number itself.
-
Repeat steps 2 and 3 until every number is circled or crossed out. The circled numbers are the primes.
To sieve up to $100$ you only need to cross out multiples of $2, 3, 5$ and $7$. The next section explains why.
At a card collectors' convention, the stands have been numbered from $10$ to $25$. The organizers want to highlight the stands that have a prime number with an orange…
At a card collectors' convention, the stands have been numbered from $10$ to $25$. The organizers want to highlight the stands that have a prime number with an orange sign. Write down the list of all the stand numbers that should have the orange sign.
The Sieve of Eratosthenes works like a filter that only lets prime numbers pass through. If we pour the numbers from $1$ to $10$ into the filter, explain why the number…
The Sieve of Eratosthenes works like a filter that only lets prime numbers pass through. If we pour the numbers from $1$ to $10$ into the filter, explain why the number $1$ is not considered prime and why the number $9$ gets trapped in the composite numbers filter.
Two numbers are said to be "twin primes" if both are prime and their difference is exactly $2$ (such as $3$ and $5$, or $11$ and $13$). a) Find all the pairs of twin…
Two numbers are said to be "twin primes" if both are prime and their difference is exactly $2$ (such as $3$ and $5$, or $11$ and $13$).
- a) Find all the pairs of twin primes between $50$ and $100$.
- b) Is it possible for there to be three consecutive odd numbers that are all prime (prime triplets)? If the answer is yes, give an example. If it is no, explain why by reasoning about divisibility by $3$.
How to Test Whether a Number Is Prime
Crossing out every number up to $601$ would take forever. A shortcut: to decide if one number $N$ is prime, divide it only by the primes up to $\sqrt{N}$.
Why does this work? Factors come in pairs that multiply to $N$. In every pair, one factor is at or below $\sqrt{N}$ and the other is at or above it.
So if $N$ had any factor besides $1$ and itself, it would have a small partner at or below $\sqrt{N}$. If you checked every prime up to $\sqrt{N}$ and found nothing, there is no such factor. A big factor can't exist without a small one.
Quick divisibility rules help with the small primes:
| Prime | Quick test |
|---|---|
| $2$ | The last digit is $0, 2, 4, 6$ or $8$ |
| $3$ | The sum of the digits is divisible by $3$ |
| $5$ | The last digit is $0$ or $5$ |
| $7, 11, 13, \dots$ | No quick rule here: just divide |
Classify the following numbers as prime or composite, justifying your answer using the divisibility rules. For the composite numbers, indicate at least one divisor other…
Classify the following numbers as prime or composite, justifying your answer using the divisibility rules. For the composite numbers, indicate at least one divisor other than $1$ and itself:
$47, 51, 67, 87, 91, 101$
In a mathematics class, the teacher says that to know if a number smaller than $100$ is prime, it is enough to check that it is not divisible by $2, 3, 5$ and $7$.…
In a mathematics class, the teacher says that to know if a number smaller than $100$ is prime, it is enough to check that it is not divisible by $2, 3, 5$ and $7$.
Justify why it is not necessary to check if it is divisible by $11$ or by other larger prime numbers. Apply this idea to check if the number $97$ is prime.
To check if the number $601$ is prime, a student claims that he only needs to divide it by the prime numbers smaller than $25$. a) Justify why the student has chosen the…
To check if the number $601$ is prime, a student claims that he only needs to divide it by the prime numbers smaller than $25$.
- a) Justify why the student has chosen the number $25$ as the limit.
- b) Carry out the necessary divisions following his reasoning and determine whether $601$ is prime or composite.
- c) What is the largest prime number you would have to test to know if $1009$ is prime?
Prime Factorization
Prime numbers are the "building blocks" of all the other numbers. Every composite number can be written as a product of primes, and in only one way (apart from the order of the factors). That product is called its prime factorization.
There are two common ways to find it.
Factor tree. Split the number into any two factors, then keep splitting every composite factor until only primes are left at the ends of the branches.
Ladder (repeated division). Divide by the smallest prime that goes in evenly, then do the same to the quotient, working up through the primes until you reach $1$. Some problems call this the vertical bar method because of the bar drawn between the number and the primes.
Repeated primes are written as a power: $2 \times 2 \times 2 = 2^3$.
Complete this "factor tree" to find the prime factorization of the number $12$. Remember that only prime numbers can be left on the final branches.
Complete this "factor tree" to find the prime factorization of the number $12$. Remember that only prime numbers can be left on the final branches.
Prime numbers are sometimes called "the building blocks of mathematics" because all other numbers are built with them. a) If you multiply $3 \cdot 3 \cdot 5$, what…
Prime numbers are sometimes called "the building blocks of mathematics" because all other numbers are built with them.
- a) If you multiply $3 \cdot 3 \cdot 5$, what composite number do you get?
- b) Is it possible to get the number $20$ by multiplying only prime numbers? Prove it by writing its factorization.
Carry out the prime factorization of the following numbers using the vertical bar method. Express the final result using powers where possible: a) $180$ b) $252$ c) $450$
Carry out the prime factorization of the following numbers using the vertical bar method. Express the final result using powers where possible:
- a) $180$
- b) $252$
- c) $450$
Factors from a Prime Factorization
The factorization is like a parts list. It tells you everything about a number's factors without dividing again and again.
Is it divisible by...? A number is divisible by $d$ exactly when the primes of $d$ fit inside the primes of the number.
Listing all the factors. Combine every power of each prime, one choice from each prime.
Find all the divisors of the following numbers using their prime factorization. Show the process of combining factors: a) $28$ b) $42$
Find all the divisors of the following numbers using their prime factorization. Show the process of combining factors:
- a) $28$
- b) $42$
Look at the following prime factorization of a "mystery" number $N$: $N = 2^{3} \cdot 3^{2} \cdot 5$ Without needing to calculate the value of $N$, answer with…
Look at the following prime factorization of a "mystery" number $N$:
$N = 2^{3} \cdot 3^{2} \cdot 5$
Without needing to calculate the value of $N$, answer with justification:
- a) Is $N$ divisible by $10$?
- b) Is $N$ a multiple of $18$?
- c) Write down three divisors of $N$ that are not prime numbers.
A natural number $N$ has the following particularity: its prime factorization is of the form $2^a \cdot 3^b$. We know that if we multiply $N$ by $2$, its number of…
A natural number $N$ has the following particularity: its prime factorization is of the form $2^a \cdot 3^b$. We know that if we multiply $N$ by $2$, its number of divisors increases by $3$, and if we multiply it by $3$, its number of divisors increases by $4$.
Calculate the value of the exponents $a$ and $b$, and find the number $N$.
Hint: Remember that if a number is $p^x \cdot q^y$, its total number of divisors is $(x + 1) \cdot (y + 1)$.
GCF and LCM from Prime Factorizations
Two numbers can share factors, and they can share multiples. Two ideas are especially useful.
Prime factorizations make both easy:
Take $36 = 2^2 \times 3^2$ and $60 = 2^2 \times 3 \times 5$.
| Prime | In $36$ | In $60$ | Smallest | Largest |
|---|---|---|---|---|
| $2$ | $2^2$ | $2^2$ | $2^2$ | $2^2$ |
| $3$ | $3^2$ | $3^1$ | $3^1$ | $3^2$ |
| $5$ | none | $5^1$ | not used | $5^1$ |
So $\text{GCF} = 2^2 \times 3 = 12$ and $\text{LCM} = 2^2 \times 3^2 \times 5 = 180$.
Two numbers are said to be coprime (or mutually prime) if their only common factor is $1$. Check if the numbers $8$ and $9$ are coprime by following these steps: 1.…
Two numbers are said to be coprime (or mutually prime) if their only common factor is $1$. Check if the numbers $8$ and $9$ are coprime by following these steps:
-
Write down all the factors of $8$.
-
Write down all the factors of $9$.
-
Circle the ones they have in common. Are they coprime?
A logistics warehouse wants to organize $120$ boxes of soft drinks and $144$ boxes of juice on identical pallets, so that each pallet has the same number of boxes of…
A logistics warehouse wants to organize $120$ boxes of soft drinks and $144$ boxes of juice on identical pallets, so that each pallet has the same number of boxes of each type and that this number is the maximum possible.
- a) How many boxes of each type will there be on each pallet?
- b) How many pallets will be needed in total?
At a young programmers' convention, they want to organize the attendees into identical teams. There are $154$ boys and $132$ girls. The goal is for each team to have the…
At a young programmers' convention, they want to organize the attendees into identical teams. There are $154$ boys and $132$ girls. The goal is for each team to have the same number of boys and the same number of girls, and for the number of teams to be the maximum possible to encourage competitiveness.
- a) How many teams will be formed and how many people will there be in each one?
- b) If for safety reasons, the teams cannot have more than $20$ people, what is the next maximum number of teams that could be formed while meeting the conditions of equality?
Word Problems: GCF or LCM?
The hardest part of a word problem is deciding which tool to use. Look for clue words.
| The problem says... | Use |
|---|---|
| split into equal groups, cut into equal pieces, "as many as possible", "as long as possible" | GCF (the answer is a size or a number of groups) |
| happens again at the same time, repeats every..., "first time again", "smallest number that works for both" | LCM (the answer is a time or a count that is a multiple) |
| leftovers: "$3$ left over" | LCM of the group sizes, then add back the leftover |
Events that repeat at regular intervals meet again at multiples of the LCM.
Three subway lines coincide at the central station at $06:00$ in the morning. Line A passes every $12$ minutes, line B every $15$ minutes, and line C every $20$ minutes.…
Three subway lines coincide at the central station at $06:00$ in the morning. Line A passes every $12$ minutes, line B every $15$ minutes, and line C every $20$ minutes.
At what time will the three lines coincide again for the first time? How many times will they have coincided in total before $10:00$ in the morning?
Sophia has a collection of old coins. If she groups them $6$ by $6$, she has $3$ left over. If she groups them $10$ by $10$, she also has $3$ left over. Knowing that she…
Sophia has a collection of old coins. If she groups them $6$ by $6$, she has $3$ left over. If she groups them $10$ by $10$, she also has $3$ left over.
Knowing that she has more than $50$ coins but fewer than $80$, exactly how many coins does Sophia have in her collection? (Hint: relate the problem to the concept of the least common multiple).
In the robotics laboratory, three drones have been programmed to emit a light signal at different intervals. Drone Alpha flashes every $45$ seconds, drone Beta every…
In the robotics laboratory, three drones have been programmed to emit a light signal at different intervals. Drone Alpha flashes every $45$ seconds, drone Beta every $60$ seconds, and drone Gamma every $72$ seconds. If all three drones are turned on simultaneously at $10:00$ in the morning:
- a) At what exact time will the three flashes coincide again for the first time?
- b) How many times will the three drones have coincided before $11:00$ in the morning (not counting the initial flash)?
Challenge Problems
These problems mix several ideas. Here are three strategies.
1. Break a product of two primes. Locking systems on the internet rely on the fact that multiplying two huge primes is easy, but finding them from the product is very hard. For numbers of our size, test the primes around $\sqrt{N}$.
A product of two different primes $p \times q$ has $(1 + 1)(1 + 1) = 4$ factors: $1$, $p$, $q$ and $pq$.
2. Build a number from required factors. "A multiple of $A$ and $B$" means a multiple of $\text{LCM}(A, B)$. Find the LCM, then list its multiples until you land in the range you are given. For instance, a number between $70$ and $100$ that is a multiple of $14$ and $21$: $14 = 2 \times 7$ and $21 = 3 \times 7$, so $\text{LCM} = 2 \times 3 \times 7 = 42$. The multiples are $42, 84, 126, \dots$, so the number is $84$.
3. Use one tool at a time. In multi-step problems, finish the first question (often a GCF), then ask yourself: "What new numbers do I have now?" and decide which tool the next question needs. To check a sum of factors (like in a "perfect number" problem), list all the factors from the prime factorization, add the ones you want, and double-check you included each exactly once.
A "perfect" number is one that is equal to the sum of all its proper divisors (all its divisors except itself). For example, $6$ is perfect because its divisors are…
A "perfect" number is one that is equal to the sum of all its proper divisors (all its divisors except itself). For example, $6$ is perfect because its divisors are $1, 2, 3$ and $1 + 2 + 3 = 6$.
- a) Check if the number $28$ is a perfect number.
- b) The next perfect number is greater than $400$ and less than $500$. Knowing that it is a multiple of $16$ and $31$, use prime factorization to find it.
In cybersecurity, very large prime numbers are used to create keys. Suppose a security key is generated by multiplying two different prime numbers, $p$ and $q$. The…
In cybersecurity, very large prime numbers are used to create keys. Suppose a security key is generated by multiplying two different prime numbers, $p$ and $q$. The result is $N = p \cdot q$.
If we know that $N = 1591$ and that one of the prime numbers is close to the square root of $N$:
- a) Find the values of $p$ and $q$.
- b) How many total divisors does the number $N$ have? Justify your answer without listing them.
We have a piece of string of $210$ in and another of $330$ in. We want to cut them into pieces of the same length, so that they are as long as possible and nothing is…
We have a piece of string of $210$ in and another of $330$ in. We want to cut them into pieces of the same length, so that they are as long as possible and nothing is left over.
- a) What length will each piece be?
- b) Once cut, we want to store all the pieces in boxes. Each box can only contain pieces from a single string (they cannot be mixed). If each box must have the same number of pieces, what is the maximum number of pieces we can put in each box so that no pieces are left over and we use the fewest possible boxes?
Back to the start: Coach Rivera's $13$ students can only make one row because $13$ is prime: its only factors are $1$ and $13$. The number $12$ is composite and has six factors ($1, 2, 3, 4, 6, 12$), so it can be arranged in many different rectangles.