Prime numbers
How can you tell whether $143$ is prime without trying to divide it by a hundred different numbers? There is a mathematical shortcut that saves you almost all of the work.
The Sieve of Eratosthenes
In a strategy video game, you need to classify energy crystals according to their purity. Crystals with prime numbers give extra energy, while composite numbers must be…
In a strategy video game, you need to classify 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 earlier numbers. Look at the following grid of numbers from $1$…
The Sieve of Eratosthenes is an ancient method for finding prime numbers by crossing out the multiples of earlier numbers. Look at the following grid of numbers from $1$ to $20$:
Copy the grid into your notebook and complete the process up to the number $50$ to identify all prime numbers less than $50$.
Checking whether a number is prime
Trying every possible divisor of a large number one by one is very slow. There is a shortcut: you only need to test the primes up to the square root.
A messaging app uses a security filter that only allows messages through if their identifier is a prime number. Classify the following identifiers as prime numbers or…
A messaging app uses a security filter that only allows messages through if their identifier is a prime number. Classify the following identifiers as prime numbers or composite numbers, justifying your decision in each case by finding a factor other than 1 and the number itself:
- a) $119$
- b) $131$
- c) $143$
- d) $151$
- e) $203$
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 reviewing 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 which two prime numbers these are, prove with reasons that they are prime using the square root method, and calculate the value of the security key $N$.
How many divisors does a number have?
If you know the prime factorisation of a number, you can work out how many divisors it has without having to list them all.
Look at the following incomplete factor tree representing the prime factorisation of a natural number. Your task is to complete it and finally write down the…
Look at the following incomplete factor tree representing the prime factorisation of a natural number. Your task is to complete it and finally write down the factorisation of that number using powers of prime factors.
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 and smallest possible "special" numbers. Next, find how many factors each of these two numbers has without needing to list them all, using only the exponents of their prime factorisations.
Back to the start: Since $\sqrt{143} \approx 11{,}96$, it is enough to test the primes $2, 3, 5, 7$ and $11$. When we divide $143 : 11 = 13$, the division is exact, so $143$ is not prime ($143 = 11 \cdot 13$).