Prime Numbers

The Fundamental Theorem of Arithmetic says that any integer greater than 1 can be written, in a unique way, as a product of prime numbers. For example, 54 = 6 × 9 and 54 = 2 × 3 × 9 are different ways of writing 54 as a product of factors; but, 54 = 2× 3 × 3 × 3 is a unique way using prime numbers!

That a number can be written in a unique way using primes, is one of the most important properties of primes numbers, because they basically give an ID to each integer greater than 1.

If you are curious about what prime and composite numbers are, get ready… We are set to learn great things about these infinitely amazing numbers!

Prime and composite numbers

A factor of a natural number is a positive divisor of it. For example, the factors of 8 are 1, 2, 4, and 8, because 8 = 8 × 1 = 2 × 4. Moreover, a proper factor of a natural number is a factor that is different from 1 and from the number itself. Thus, the proper factors of 8 are 2 and 4.

A natural number is called a prime number if it is greater than 1, and it doesn’t have proper factors. For example, the only factors of 2 are 1 and 2. Thus, 2 doesn’t have proper factors, and it is, therefore, a prime number.

A composite number is a natural number that has proper factors. As we saw, 8 is a composite number.

Let’s explore more differences between prime and composite numbers.

For example, 3 = 1 × 3 doesn’t have proper factors, because 2 doesn’t divide it: 3 = (2×1) + 1. Thus, 3 is a prime number.
Number 6, instead, has two proper factors: 2 and 3, because 6 = 2 × 3. Meaning that 6 is a composite number.

The difference between 3 and 6 is like in the image: 3 comes alone to the party, and 6 comes with two of its friends: the proper factors 2 and 3. Number 6 is composed of numbers different from itself, but 3 is not.

Another way of differentiating a composite number from a prime number is noticing that a composite number can be split into equal parts having more than one element, but a prime number cannot.

For example, 6 can be split into 2 parts with 3 elements each; or into 3 parts with 2 elements each, as shown below. Contrarily, the prime number 3 can only be split into equal parts, if each part has one element.

We are not claiming that every odd number is a prime number. That is, in fact, not true. For example, 9 is an odd number, but it can be split into three equal parts of more than one element. Thus, 9 is a composite number.

Let’s discuss more examples.

Example 1: Is 21 a prime number?

To answer this question, we should verify if 21 has proper factors. But, where do we look for proper factors? In the list: 2, 3, 4, 5, 6, 7, 8, …, 19, 20, of all natural numbers greater than 1, and less than 21.

Let’s see if one of them divides 21. Since 21 is not even, 2 doesn’t divide 21. We continue with 3, and we notice that 21 = 3 × 7. Meaning that both 3 and 7 are proper factors of 21, thus 21 is a composite number. In other words, 21 is not a prime number.

As we see, the concept of “prime number” is linked to that of “composite number” because any natural number greater than 1 is either prime or composite. Also, the main procedure to determine if a number is prime is verifying if it has proper factors.

In the previous example, we were lucky to find proper factors for 21 at the beginning of that long list; but, what if the number is too big and we don’t find a proper factor quickly?

Well, the first guess is to think that the number in fact doesn’t have a proper factor, and therefore it is prime. Unfortunately, we cannot be sure of that until we check that enough numbers are not proper factors of our number. Luckily, we are about to know a property that shortens the list where to look for proper factors of a number.

How to determine if a number is prime?

This is a question that mathematicians have tried to answer for centuries. First of all, there isn’t a formula to generate all prime numbers. Additionally, prime numbers can be as big as we can imagine, and between two prime numbers may be an enormous amount of composite numbers.

Making history short, it isn’t an easy job determining if a number is prime. But, don’t worry! In this article, we will only work with small primes that we know how to identify.

Here are some rules to determine if a number is prime:

• Any number, different from 2, ending in 0, 2, 4, 6, or 8 is not a prime number: If a number ends in 0, 2, 4, 6, or 8, it is even; but, the only even prime number is 2.
  Notice that 2 is a proper factor of any even number greater than 2, therefore they are all composite numbers. For example, 872 is not prime because 872 = 2 × 436.
  This gives us a huge (infinite) list of non-prime numbers: 4, 6, 8, 10, 12… 4230…, 5668, etc.
• Any number, different from 5, ending in 5 is not a prime number: First, notice that 5 is prime because neither of 2, 3, and 4 is a proper factor of 5.
  Besides, 5 is a proper factor of any number ending in 5 and greater than 5. Therefore, they are all composite numbers. For example, 125 = 5 × 25, which means that 125 isn’t a prime. The same can be said about 35, 85, 745, etc.
• Every prime number is has a form 👉🏻  6k+1 or 6k+5: Therefore, if a number is not 👉🏻  6k+1 or 6k+5, it can’t be prime. In other words, if the remainder when a number is divided by 6 is different from 1 or 5, then the number is not prime. For example, 39 = 6(6) + 3. Thus, the remainder when 39 is divided by 6 is 3 (different from 1 and 5). It follows that 39 is not prime! Can you find a proper factor for 39? Nevertheless, you need to be very careful with this rule, because its converse is not true!
  
  For example, 25 = 6(4) + 1 is of the form 6k+1, but 25 is not prime because it ends in 5!
  So, be sure to use this rule just in the right direction.
• If 𝒏 is a natural number and neither of the prime numbers less than
  $$\sqrt n$$ divides 𝒏, then 𝒏 is a prime number. We will explain this result with a couple of examples. Suppose that we want to determine if n = 23 is prime. First, notice that 23 < 25, thus$$\sqrt{23}<\sqrt{25}=5$$.Then, the prime numbers less than

  $$\sqrt{23}$$ are 2, and 3.
  Now, 23 = 2(11) + 1 and 23 = 3(7) + 2; thus, neither 2 nor 3 divides 23. Then, we conclude that 23 is a prime number!
  This is like magic! don’t you think? If we had followed the procedure made in previous examples, we would verify if any of 2, 3, 4, …, 21, 22 divides 23. That is a long list! But, with this result, we only needed to check a list with two numbers on it. Let’s consider another example: we want to determine if n = 27 is a prime number.Notice that 27 < 36, thus

  $$\sqrt{27}<\sqrt{36}=6$$. Then, the prime numbers less than

  $$\sqrt{27}$$ are: 2, 3 and 5. We should check if any of them divides 27.
  
  Indeed, 27 = 3 × 9. It follows that 27 has proper factors, and therefore 27 is not prime.

These rules are very useful especially to determine if a big number is prime. As for the prime numbers between 1 and 100, we have a special procedure to list them all.

Prime numbers between 1 and 100

To find all prime numbers between 1 and 100, we will follow a procedure called Sieve of Eratosthenes, after its inventor. This procedure consists in listing all numbers between 1 and 100, and then crossing out the multiples of a prime step by step. At the end, we are left with primes between 1 and 100.

We start crossing out 1, because it isn’t a prime number, as we will discuss in another article. Then, we cross out all multiples of 2, except 2 itself. This step is shown in red in the image below.

In a second step, we crossed out the multiples of the next prime number: 3, except 3 itself. This step is shown in blue.

Then, we cross out all multiples of 5, except 5. This step is shown in yellow.

The number that follows 5, after the previous step, is 7. This number has to be prime! Why? Because it wasn’t crossed out before, meaning it isn’t multiple of 2, 3 or 5.

We continue repeating this procedure, with 7, 11, 13, etc., until there are not numbers to cross out.

The numbers left (shown in green) are those without proper factors; that is, the 25 prime numbers between 1 and 100:

Prime Numbers between 1 and 100
2	3	5	7	11
13	17	19	23	29
31	37	41	43	47
53	59	61	67	71
73	79	83	89	97

Of course, you don’t need to do this procedure each time you want to find a prime number between 1 and 100, you can look for them on this list, or memorize them instead!

On a fresh chart, color all of the crossed-out numbers one color and all of the circled numbers another. Give 1 a color of its own. On our chart, we colored the prime numbers yellow and left the composite numbers white. We made 1 blue.

You can see that there are 25 prime numbers between 1 and 100. There are 74 composite numbers and then, of course, there’s 1 which is neither prime nor composite. Did your chart match ours?

Nicely done!

Did you know that…

The largest prime number , known until September 2021, is

$$2^{82,589,933}-1$$?

This number was found with the help of a computer and has 24,862,048 digits!!

How many prime numbers there are?

We have just met the first 25 prime numbers. However, there are so many more primes numbers, that we can’t count them… There are infinitely many prime numbers! But only some of them are known.

To understand why there are so many, let’s first study some numbers:

• The number (2×3) + 1 is the product of the first two prime numbers plus 1. It is equal to 7, and 7 is prime!
• The number (2×3×5) + 1 is the product of the first three prime numbers plus 1. It is equal to 31, and the list above says it is prime!
• Continuing this pattern: 211 = (2×3×5×7) + 1 and 2311 = (2×3×5×7×11) + 1 are also prime numbers. You can verify that using rule 4, for example.

Does it mean that whenever $$\operatorname{𝑝}_1,\operatorname{𝑝}_2,\operatorname{𝑝}_3,\dots,\operatorname{𝑝}_n$$ are the first 𝑛 primes, the number

$$\operatorname{𝑎}=(\operatorname{𝑝}_1\times\;\operatorname{𝑝}_2\times\;\operatorname{𝑝}_3\times\dots\times\;\operatorname{𝑝}_n)+1$$

Is also prime? Unfortunately, no! For example,

(2×3×5×7×11×13) + 1 = 30,031 = 59 × 509.

Thus, 30,031 is the product of the first six prime numbers plus 1, but it is composite. Remember, there isn’t a formula to find all prime numbers!

However, from the expression 30,031 = (2×3×5×7×11×13) + 1 we can conclude that the remainder of dividing 30,031 by 2, 3, 5, 7, 11 or 13, is equal to 1. Thus, neither of 2, 3, 5, 7, 11 and 13 divides 30,031.

Now, let’s be stubborn for a moment, and assume that there are finitely many prime numbers, and that we can list them all:

$$\operatorname{𝑝}_1,\operatorname{𝑝}_2,\operatorname{𝑝}_3,\dots,\operatorname{𝑝}_n$$. Then, as before, neither of them divides the number

$$\operatorname{𝑎}=(\operatorname{𝑝}_1\times\;\operatorname{𝑝}_2\times\;\operatorname{𝑝}_3\times\dots\times\;\operatorname{𝑝}_n)+1.$$

This means that 𝑎 is a prime number, because none of all the primes numbers divides it. But, wait a minute! We have listed all the prime numbers, and 𝑎 wasn’t on that list! That means the list is incomplete.... Don’t be stubborn! There are infinitely many of them.

The prime numbers are amazing! If you still have questions about prime numbers, we invite you to read the related articles mentioned below.

Are these prime numbers?
Is 1 a Prime Number?	Is 47 a Prime Number?
Is 2 a Prime Number?	Is 49 a Prime Number?
Is 5 a Prime Number?	Is 51 a Prime Number?
Is 7 a Prime Number?	Is 57 a Prime Number?
Is 9 a Prime Number?	Is 59 a Prime Number?
Is 11 a Prime Number?	Is 61 a Prime Number?
Is 13 a Prime Number?	Is 63 a Prime Number?
Is 17 a Prime Number?	Is 67 a Prime Number?
Is 19 a Prime Number?	Is 71 a Prime Number?
Is 23 a Prime Number?	Is 79 a Prime Number?
Is 29 a Prime Number?	Is 83 a Prime Number?
Is 31 a Prime Number?	Is 89 a Prime Number?
Is 37 a Prime Number?	Is 91 a Prime Number?
Is 41 a Prime Number?	Is 97 a Prime Number?
Is 43 a Prime Number?	Is 101 a Prime Number?

Take a quiz

Question 1Review: Prime and composite numbers

What key idea does the article explain about “Prime and composite numbers”?

Answer

A factor of a natural number is a positive divisor of it. For example, the factors of 8 are 1, 2, 4, and 8, because 8 = 8 × 1 = 2 × 4. Moreover, a proper factor of a natural number is a factor that is different from 1 and from the number itself. Thus, the proper factors of 8 are 2 and 4.A natural number is called a prime number if it is greater than 1, and it doesn’t have proper factors. For example, the only factors of 2 are 1 and 2. Thus, 2 doesn’t have proper factors, and it is, therefore, a prime number.A composite number is a natural number that has proper factors. As we saw, 8 is a compo

Question 2Review: How to determine if a number is prime?

What key idea does the article explain about “How to determine if a number is prime?”?

Answer

This is a question that mathematicians have tried to answer for centuries. First of all, there isn’t a formula to generate all prime numbers. Additionally, prime numbers can be as big as we can imagine, and between two prime numbers may be an enormous amount of composite numbers.Making history short, it isn’t an easy job determining if a number is prime. But, don’t worry! In this article, we will only work with small primes that we know how to identify.Here are some rules to determine if a number is prime:Any number, different from 2, ending in 0, 2, 4, 6, or 8 is not a prime number: If a numb

Question 3Review: Prime numbers between 1 and 100

What key idea does the article explain about “Prime numbers between 1 and 100”?

Answer

To find all prime numbers between 1 and 100, we will follow a procedure called Sieve of Eratosthenes, after its inventor. This procedure consists in listing all numbers between 1 and 100, and then crossing out the multiples of a prime step by step. At the end, we are left with primes between 1 and 100.We start crossing out 1, because it isn’t a prime number, as we will discuss in another article. Then, we cross out all multiples of 2, except 2 itself. This step is shown in red in the image below.In a second step, we crossed out the multiples of the next prime number: 3, except 3 itself. This s

Question 4Review: Did you know that…

What key idea does the article explain about “Did you know that…”?

Answer

The largest prime number , known until September 2021, is$$2^{82,589,933}-1$$?This number was found with the help of a computer and has 24,862,048 digits!!

Question 5Review: How many prime numbers there are?

What key idea does the article explain about “How many prime numbers there are?”?

Answer

We have just met the first 25 prime numbers. However, there are so many more primes numbers, that we can’t count them… There are infinitely many prime numbers! But only some of them are known.To understand why there are so many, let’s first study some numbers:The number (2×3) + 1 is the product of the first two prime numbers plus 1. It is equal to 7, and 7 is prime!The number (2×3×5) + 1 is the product of the first three prime numbers plus 1. It is equal to 31, and the list above says it is prime!Continuing this pattern: 211 = (2×3×5×7) + 1 and 2311 = (2×3×5×7×11) + 1 are also prime numbers. Y

 

Prime Numbers in the Real World

Prime numbers are far more than just a cool math thing to know. Prime numbers are used daily by encryption specialists to secure some of the most valuable assets in the world.

By multiplying two large prime numbers together, we are able to achieve an extremely large and nearly un-factorable number to be used in encryption.

Right now, prime numbers are also being used to establish the color intensity of pixels on your screen.

Prime numbers are even found in nature. Cicadas, for example, time their life cycles based on prime numbers.

The bottom line is, that whether or not you know it, you depend on prime numbers each and every day.

Video Lecture

[embed]https://vimeo.com/246876494[/embed]

Love our videos? Check out our incredible learning platform for students from Kindergarten through 8th grade.