Ultimate Guide To Prime Numbers
Mathematics is a fascinating field of study with many interesting concepts, patterns, theories, and innovative ways of thinking about the world.
Prime numbers are one of the most well-known ideas in mathematics. They are whole numbers with unique characteristics that make them useful for certain types of mathematical calculations.
In this guide, I’m going to delve into the world of prime numbers. I’ll explain what prime numbers are, why prime numbers are important, and how to identify prime numbers.
What Are Prime Numbers?
To understand what a prime number is, you will need to learn what a “natural number” is. A natural number refers to any positive integer that does not have a fraction attached to it. This includes numbers like 3, 4, 7, 10, 1000, and 165738.
A prime number is any positive natural number that is only evenly divisible by one and itself.
The number 5 is a prime number because it can only be divided by one (5 / 1 = 5) or itself (5 / 5 = 1) and remain a natural number. If 5 is divided by 2 or 3, you would end up with a fraction (2.5 and 1.6666667 respectively).
Prime numbers like 5 have no divisor. A divisor is a number that divides evenly into another number without a remainder (other than 1 or the number itself).
Another way of describing prime numbers is that they are numbers which cannot be formed by multiplying two smaller natural numbers.
So, if we take another look at 5, you would notice that it can only be created by multiplying 1 x 5. It cannot be created by multiplying 2, 3, or 4 with any other number.
Let’s take a look at a non-prime number to make sure you understand the difference. Consider the number 6.
Is 6 a positive natural number that is only evenly divisible by one and itself? No, because 6 can be divided by 2 (6/2 = 3) or 3 (6 / 3 = 2) and return natural numbers. 6 can also be created by multiplying two smaller natural numbers (3 x 2 = 6).
Non-prime natural numbers like 6 are called composite numbers. They can always be formed by multiplying two smaller natural numbers.
The Characteristics of Prime Numbers
Prime numbers have certain characteristics which make them easier to identify, including:
1. There is only one even prime number
The only even prime number is 2. That’s because every other even number can be divided by 2, which makes them composite numbers. This fact immediately halves the number of potential prime numbers that are available.
2. Zero and 1 are not prime numbers
If mathematicians considered these numbers prime, then there would be no other prime numbers, as all whole numbers are divisible by 1.
3. If the sum of a number’s digits is a multiple 3 it is not a prime number
This characteristic helps us eliminate potential prime number candidates. To give you an example, if you add the digits contained within 261, you would get 9 (2 + 6 + 1 = 9) — which is divisible by 3. This rules tells us that it will not be a prime number, and we can confirm that by calculating 261 / 3, which equals 24.
This technique lets us analyse large numbers very quickly to determine if they are prime. Here’s another example. Let’s say you wanted to check if 945,327 was a prime number. By adding 9 + 4 + 5 + 3 + 2 + 7 you would get 30. 30 is divisible by 3 which tells us it is not prime. We can confirm this fact by dividing 945,327 by 3, which gives us 315,108.
4. No prime number greater than 5 ends in a 5
This is another rule which makes identifying prime numbers easier. Any number ending in a 5 (other than 5) will be divisible by 5 and therefore cannot be a prime number. That means you can immediately rule out large numbers like 1,089,385 as potential prime numbers. This rule also means that numbers ending in 0 will never be prime, as they can also be divided by 5 or 10.
5. Prime numbers become less frequent
If you count from 1 to 100, you will come across 25 prime numbers. This might fool you into thinking that prime numbers are extremely common. However, the higher you count, the less common they become.
The prime number characteristics give us a basic process for finding them. For example, if you were trying to determine if 509 was a prime number, you could check:
1. Is the number even?No, so it could still be a prime number.
2. Does the number end in a 5 or a 0?No, so it could still be a prime number.
3. Is the sum of the number’s digits a multiple 3?5 + 0 + 9 = 14, which is not a multiple of 3, so it could still be a prime number.
Although it is likely that 509 is a prime number, you would have to do more testing to ensure that is the case. There are multiple methods for finding and testing prime numbers which we’ll share below.
Why Are Prime Numbers Important?
Prime numbers are important for several reasons. The most interesting reason being that the entire number line (1 to infinity) can be created only using prime numbers.
To give you an example, the number 12 can be expressed using 2 x 2 x 3 = 12 (2 and 3 are both prime numbers). The number 161 can be computer using 7 x 23 (both prime numbers), while the number 5476 can be calculated using 2 x 2 x 37 x 37 (again, all prime numbers).
The process of breaking numbers into primes is called the prime factorisation of a number. There are online calculators which can show you who prime factors of a number or you can also calculate prime factors manually.
While you can calculate the prime factors of small numbers easily, it becomes very difficult to calculate prime factors for larger numbers. For example, the prime factors of 9879791 are 19 and 519989. Most people would not even be aware that 519989 is a prime number.
When numbers become extremely large, advanced computing power and algorithms are required to find prime factors. In fact, it would take a super-computer a few million years to calculate the prime factors of a 256-bit number.
The difficulty of using prime factors to calculate huge numbers becomes useful in fields like cryptography. Programmers can use a large number to encrypt a file and publicly display that number. To decrypt the file, the user must enter the prime factors of that number. It would be extremely difficult for a person or computer program to guess the prime factors involved.
Because prime numbers are the building blocks of whole numbers, they are also used by mathematicians in other fields including abstract algebra, quantum mechanics, and biology.
Finding Prime Numbers
There are several techniques for finding prime numbers. They range from basic strategies for finding low numbers through to complex computational algorithms for uncovering huge prime numbers.
Checking a number's divisibility
The simplest strategy for finding prime numbers is to check if the number can be divided by anything other than 1 and itself. For example, if we were checking the status of 89, we could manually check if it could be divided by 2, 3, 4, 5…n and return a whole number. Computer programs can be created to perform this task, however this process becomes extremely time consuming when checking large numbers.
A better technique would be to check if the candidate number can be divided by prime numbers. This works well because prime numbers are the building blocks of all other numbers, so when we check for primes we are effectively checking for all other numbers at the same time. So, we could simply check if 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, etc, can evenly divide into 89.
This basic divisibility method can be improved even more with the help of a little bit of simple logic. If n is not a prime number, it must be the product of two other numbers multiplied together, like so:
What do we know about a and b? One thing we know is that they can’t both be larger than the square root of n. That’s because multiplying two numbers larger than the square root of n would give us a total larger than n (like multiplying 5 x 4 would give us more than 16).
This means that either a or b is lower than the square root of n. This information helps us reduce how many numbers we need to check.
To give you a quick example, if we were checking if 89 was a prime number, we could calculate √89, which is 9.43398113206. We now know that a or b must be is smaller than 9.43398113206.
This means we only need to check for prime numbers lower than 9.4, which are 2, 3, 5, and 7. 89 is not evenly divisible by any of those numbers, which means we are dealing with a prime number.
Prime Sieves are algorithms that are designed to make it easier to find primes. Many prime sieves have been developed over the centuries including the sieve of Eratosthenes (250s BCE), the sieve of Sundaram (1934), and the sieve of Atkin (2004).
The most basic prime sieve is the sieve of Eratosthenes. It uses a table to find the multiples of numbers and mark them as composite numbers.
If you were using this method to look for prime numbers below 100, you would create a grid with 10 rows and 10 columns with the numbers 1 to 100 in each cell. You would then start by looking for numbers which are divisible by the first prime number in the number range (which is 2). You could disqualify those numbers as they are composite numbers.
Next, you would look for all of the numbers which are divisible by 3 and disqualify them. You would move onto 5, then 7. It’s safe to stop checking numbers when you reach 11, because 11 squared is 121, which is greater than 100.
You wouldn’t have to look for numbers which are divisible by 4, 6, 8, or 9 because they would have been identified when you checked for 2 and 3.
While this method is suitable for checking for low prime numbers, it would be extremely time consuming when looking for larger prime numbers. For larger numbers, standard probabilistic primality tests like the Baillie–PSW primality test or the Miller–Rabin primality test are often used (Read more about the generation of large prime numbers).
I hope you enjoyed reading the Ultimate Guide To Prime Numbers. Prime numbers are a fascinating topic and an important area of mathematics. For more articles, subscribe to our website.