Prime Numbers
Jayden says, "$143$ must be prime. It's not divisible by $2$, $3$, $5$, or $7$." Is he right? You will be able to settle this in about ten seconds, with no long list of divisions.
Primes, composites, and the Sieve of Eratosthenes
Examples: $7$ is prime (only $1$ and $7$ divide it). $12$ is composite ($1, 2, 3, 4, 6, 12$). The number $2$ is the only even prime, because every other even number is also divisible by $2$.
How do you find all the primes up to some limit? About 2,200 years ago, the Greek mathematician Eratosthenes had a clever idea: instead of testing numbers, cross out the multiples of each prime. Whatever survives is prime.
The highlighted boxes are the primes $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$. Here is how the sieve produces them.
When can you stop? You only need to cross out multiples of primes $p$ with $p^2 \le$ your limit. For a list up to $30$, you stop after $5$, because $7^2 = 49$ is already bigger than $30$. For a list up to $50$, you also need to cross out the multiples of $7$.
In a strategy video game, you need to classify the energy crystals according to their purity. Crystals with prime numbers give extra energy, while composite numbers must…
In a strategy video game, you need to classify the energy crystals according to their purity. Crystals with prime numbers give extra energy, while composite numbers must be processed.
Classify the following numbers in the table in your notebook:
$11, 15, 23, 27, 31, 39, 42, 47, 51$
The Sieve of Eratosthenes is an ancient method for finding prime numbers by crossing out the multiples of previous numbers. Look at the following chart of the numbers…
The Sieve of Eratosthenes is an ancient method for finding prime numbers by crossing out the multiples of previous numbers. Look at the following chart of the numbers from $1$ to $20$:
Copy the grid into your notebook and complete the process up to the number $50$ to identify all the prime numbers less than $50$.
Twin prime numbers are pairs of prime numbers that are separated only by an even number (that is, their difference is $2$). For example, $3$ and $5$ are twin primes. a)…
Twin prime numbers are pairs of prime numbers that are separated only by an even number (that is, their difference is $2$). For example, $3$ and $5$ are twin primes.
- a) Find all the pairs of twin prime numbers less than $60$.
- b) Is the pair $(21, 23)$ a pair of twin primes? Justify your answer.
Divisibility rules
To decide whether a number is prime, you need to spot divisors fast. Divisibility rules let you do that without dividing.
| Divisible by | Rule |
|---|---|
| $2$ | The last digit is $0, 2, 4, 6,$ or $8$. |
| $3$ | The sum of the digits is a multiple of $3$. |
| $4$ | The number formed by the last two digits is a multiple of $4$. |
| $5$ | The last digit is $0$ or $5$. |
| $6$ | It is divisible by both $2$ and $3$. |
| $9$ | The sum of the digits is a multiple of $9$. |
| $10$ | The last digit is $0$. |
| $11$ | The alternating sum of the digits (add, subtract, add, … starting from the right) is $0$ or a multiple of $11$. |
Why do these work? Because $10$, $100$, … leave a remainder of $1$ when divided by $3$ or $9$, so only the digit sum matters. And because $100$ is a multiple of $4$, only the last two digits matter for $4$.
To organize the shelves of a school library, the librarian uses the rules of divisibility. Without performing long division, indicate which of the following numbers are…
To organize the shelves of a school library, the librarian uses the rules of divisibility. Without performing long division, indicate which of the following numbers are divisible by $3$ and which by $5$:
- a) $123$
- b) $405$
- c) $1.020$
- d) $715$
Did you know that prime numbers are used to create security codes on the internet? A secret code is a prime number greater than $40$ and less than $50$. What numbers…
Did you know that prime numbers are used to create security codes on the internet? A secret code is a prime number greater than $40$ and less than $50$. What numbers could the code be? Check your answer using the rules of divisibility.
In an online strategy game, to unlock a chest you need to enter a four-digit key of the form $52X4$. If the system tells you that the key is a number divisible by $3$…
In an online strategy game, to unlock a chest you need to enter a four-digit key of the form $52X4$. If the system tells you that the key is a number divisible by $3$ and by $4$ simultaneously, what are all the possible values that the digit $X$ can take? Reason your answer by applying the corresponding rules of divisibility.
Testing whether a number is prime
A sieve is great for a list, but what if you only need to test one big number? You can't try every possible divisor. Here is the shortcut.
Why is that enough? If $N = a \cdot b$ and $a \le b$, then $a \cdot a \le a \cdot b = N$, so $a \le \sqrt{N}$. Every composite number therefore has a divisor at or below its square root. If you haven't found one by then, there isn't one.
You don't need a calculator to find the limit. Sandwich $N$ between two perfect squares: $10^2 = 100 < 113 < 121 = 11^2$, so $\sqrt{113}$ is between $10$ and $11$.
A messaging app uses a security filter that only allows messages whose identifier is a prime number to pass. Classify the following identifiers into prime numbers or…
A messaging app uses a security filter that only allows messages whose identifier is a prime number to pass. Classify the following identifiers into prime numbers or composite numbers, justifying your decision in each case by finding a divisor other than one and the number itself:
- a) $119$
- b) $131$
- c) $143$
- d) $151$
- e) $203$
Find the value of the digit $X$ so that the number $35X1$ is a prime number. To do this, follow these steps: 1. Apply the rules of divisibility to rule out values of $X$…
Find the value of the digit $X$ so that the number $35X1$ is a prime number. To do this, follow these steps:
-
Apply the rules of divisibility to rule out values of $X$ that make it divisible by $3$ or $11$.
-
From the remaining values, use the square root method to check which of them generates a prime number. Bear in mind that you only need to test for divisibility by prime numbers up to the integer part of $\sqrt{35X1}$.
A cybersecurity expert is designing an encryption system for a messaging app. The main security key is a number $N$ obtained by multiplying a pair of twin prime numbers…
A cybersecurity expert is designing an encryption system for a messaging app. The main security key is a number $N$ obtained by multiplying a pair of twin prime numbers between $100$ and $110$. However, upon checking the list, he realizes that there are two pairs of twin primes in that interval, so the choice is not unique. To solve the problem, he decides that the key will be the product of the two prime numbers closest to $105$ (one below and one above).
Determine what these two prime numbers are, check with reasoning that they are prime using the square root method, and calculate the value of the security key $N$.
Prime factorization
Every composite number can be written as a product of primes, its prime factorization. This is like finding the "atoms" of the number. Two methods work well.
Factor tree. Split the number into any two factors, then keep splitting each composite factor until every branch ends in a prime.
Division ladder. Divide by the smallest prime that works, then divide the quotient again, and so on until you reach $1$. (Some problems call this the "vertical line" method.)
Write repeated factors with exponents, and list the primes from smallest to largest, like $2^2 \cdot 3^2 \cdot 5$.
In Math class we are learning to break down numbers into their fundamental building blocks: prime factors. Perform the prime factorization (using the "vertical line") of…
In Math class we are learning to break down numbers into their fundamental building blocks: prime factors. Perform the prime factorization (using the "vertical line") of the following numbers:
- a) $24$
- b) $60$
- c) $100$
Look at the following incomplete factor tree that represents the factorization of a natural number. Your task is to complete it and finally write the prime factorization…
Look at the following incomplete factor tree that represents the factorization of a natural number. Your task is to complete it and finally write the prime factorization of this number using powers of prime factors.
An architect is designing a circular plaza and wants to place streetlights on the edge. The number of streetlights must be a prime number $n$. For the lighting to be…
An architect is designing a circular plaza and wants to place streetlights on the edge. The number of streetlights must be a prime number $n$. For the lighting to be aesthetic, the architect has discovered that if he subtracts 1 from the number of streetlights $(n-1)$, the result must be a number whose prime factorization is $2^3 \cdot 3^2$.
Calculate the value of $n$, justify why it is a prime number and represent the prime factorization of the composite number $(n-1)$ in a factor tree.
Divisors and how many there are
The prime factorization is a recipe for every divisor. A divisor of $12 = 2^2 \cdot 3$ uses $2^0, 2^1,$ or $2^2$, times $3^0$ or $3^1$. Combine every choice:
The grid has $3 \times 2 = 6$ cells. Notice that $3 = 2 + 1$ (the exponent $2$ plus one) and $2 = 1 + 1$. That pattern always works.
Why $a + 1$? The exponent of $p$ in a divisor can be $0, 1, 2, \dots, a$, and that is $a + 1$ choices. Choices for different primes multiply.
Two useful special cases. A prime $p = p^1$ has $1 + 1 = 2$ divisors. A power of a prime $p^k$ has $k + 1$ divisors, for example $3^4 = 81$ has $5$.
A programmer is creating a list of all the divisors of the number $30$ for a security algorithm. Use its prime factorization to find all its natural divisors. Hint:…
A programmer is creating a list of all the divisors of the number $30$ for a security algorithm.
Use its prime factorization to find all its natural divisors.
Hint: Remember that $1$ and the number itself are always divisors.
In a rhythmic gymnastics exhibition, there is a group of $p$ gymnasts. The choreographer tries to organize the athletes into rows and columns to form a perfect…
In a rhythmic gymnastics exhibition, there is a group of $p$ gymnasts. The choreographer tries to organize the athletes into rows and columns to form a perfect rectangle, but observes that the only way to do so is by placing them all in a single row. By adding one more gymnast to the group, the total number of people $(p+1)$ becomes a number that has exactly 8 divisors.
If it is known that $40 < p < 60$, identify all possible values of $p$, show that $p$ is a prime number and find all the possible ways to organize the group of $(p+1)$ gymnasts into rectangles of more than one row.
A natural number is said to be "special" if it is the product of three distinct prime numbers less than $20$. An example would be $2 \cdot 3 \cdot 5 = 30$. Find the…
A natural number is said to be "special" if it is the product of three distinct prime numbers less than $20$. An example would be $2 \cdot 3 \cdot 5 = 30$.
Find the largest possible "special" number and the smallest possible one. Then, find out how many divisors each of these two numbers has without needing to list them all, using only the exponents of their prime factorization.
GCF and LCM with prime factorization
Two kinds of problems keep coming up.
How do you tell which one a word problem wants?
| Clue in the problem | Use |
|---|---|
| Split into equal groups, nothing left over, as many (or as large) as possible | GCF |
| Two or more things repeat and you want the next time they happen together | LCM |
With prime factorizations, both are quick.
The reason: a divisor of both numbers can only use primes that both have, and no more of each than the smaller exponent allows. A common multiple must contain at least as much of every prime as either number does.
A candy shop wants to pack $20$ strawberry lollipops and $28$ lemon lollipops into identical bags, so that they have the maximum number of lollipops possible without…
A candy shop wants to pack $20$ strawberry lollipops and $28$ lemon lollipops into identical bags, so that they have the maximum number of lollipops possible without mixing them. To do this they must calculate the Highest Common Factor (HCF).
Calculate the HCF of $20$ and $28$ and explain how many lollipops there will be in each bag.
Two friends are running on a circular track. Ashley takes $8$ minutes to complete a lap and Ethan takes $12$ minutes. If they start together from the finish line, how…
Two friends are running on a circular track. Ashley takes $8$ minutes to complete a lap and Ethan takes $12$ minutes. If they start together from the finish line, how many minutes will pass until they coincide again for the first time at the finish line?
Use the lowest common multiple (LCM) to solve it.
A food bank has received a donation of $120$ jars of beans, $150$ gallons of milk and $72$ cans of preserves. They want to prepare the greatest possible number of…
A food bank has received a donation of $120$ jars of beans, $150$ gallons of milk and $72$ cans of preserves. They want to prepare the greatest possible number of identical boxes to distribute to families in need, with nothing left over from any product.
- a) How many boxes can they prepare as a maximum?
- b) What quantity of each product will each of these boxes contain?
Coprime numbers and a GCF × LCM shortcut
Coprime numbers need not be prime themselves: $8$ and $15$ are both composite, but $8 = 2^3$ and $15 = 3 \cdot 5$ share nothing. Two different primes are always coprime. When two numbers are coprime, there are no shared primes to "reuse", so the LCM is just their product. For $8$ and $15$, $\text{LCM} = 120$.
There is also a handy relationship for any two numbers.
Why? Take each prime separately. The GCF gets the smaller exponent and the LCM gets the larger, so together they use both exponents, just like $a$ and $b$ do. This lets you find a missing number.
Calculate the numerical value of the numbers $A$ and $B$ from their prime factorizations and, subsequently, find the $m.c.m.(A, B)$ and the $m.c.d.(A, B)$.…
Calculate the numerical value of the numbers $A$ and $B$ from their prime factorizations and, subsequently, find the $m.c.m.(A, B)$ and the $m.c.d.(A, B)$.
$A = 2^{3} \cdot 3^{2} \cdot 5$
$B = 2^{2} \cdot 3 \cdot 5^{2}$
Indicate whether $A$ and $B$ are coprime and explain why based on the result of the highest common factor.
It is known that the highest common factor of two numbers is $m.c.d.(a, b) = 15$ and that their product is $a \cdot b = 6750$. Use the mathematical relationship between…
It is known that the highest common factor of two numbers is $m.c.d.(a, b) = 15$ and that their product is $a \cdot b = 6750$. Use the mathematical relationship between the product of two numbers and their common factors/multiples to find the lowest common multiple of these numbers without needing to calculate them separately.
Two comets pass close to Earth periodically. Comet A passes every $p$ years, where $p$ is a prime number. Comet B passes every $q$ years, where $q$ is the next…
Two comets pass close to Earth periodically. Comet A passes every $p$ years, where $p$ is a prime number. Comet B passes every $q$ years, where $q$ is the next consecutive prime number to $p$. It is known that the last time they coincided was $77$ years ago and that this was the first time they were seen since historical records began.
If $p$ and $q$ are two-digit numbers, identify which numbers they are and calculate how many years will have to pass for them to coincide again.
Back to the start: Jayden tested $2, 3, 5,$ and $7$ and stopped there. But $11^2 = 121 < 143 < 144 = 12^2$, so the square root test says he also has to try $11$. And $143 \div 11 = 13$ exactly, so $143 = 11 \cdot 13$ is composite. The alternating sum $3 - 4 + 1 = 0$ would have told him that $11$ divides $143$ in seconds.