# Prime Numbers

**Table of Contents**

1. | Introduction |

2. | What are Prime Numbers? |

3. | List/Chart/History(Background) of Prime Numbers |

4. | Twin-Primes and Co-Primes |

5. | Sieve of Eratosthenes |

6. | FAQs |

09 October 2020

**Read time: 8 minutes**

**Introduction**

This article endeavors to provide a ground and even a bridge between theory and experiment in the matter of prime numbers. Prime numbers belong to an exclusive world of intellectual conceptions. Prime Numbers enjoy simple, elegant description, yet complex in detail. The article tasks to find, characterize and apply the primes in various domains.

It is a straight forward math concept and as you progress through your mathematical career, you will see that there are actually fairly sophisticated concepts that can be built on the top of the idea of prime* numbers*.

**What are Prime Numbers?**

A *prime number* is a positive integer (let us denote the prime number as *p* for further reference) having exactly two positive divisors, namely 1 and *p* itself.

In other words, a number is defined as a *prime number*, if it is a natural number (1 2 3… that is positive integers) divisible by exactly two different natural numbers. One of those numbers is 1 and the other one is the number itself. These are the two numbers it is divisible by.

Another form to define a prime number is that it cannot be broken further into a product of two natural numbers other than 1 and itself.

Let us start with the smallest natural number.

Remember to use the **Conditions**

**Condition 1**

*p* should be a Positive Integer

**Condition 2**

*p* should be exactly divisible by two different natural numbers, yielding remainder as zero

**Condition 2a**

*p* should be divisible by 1

**Condition 2b**

*p* should be divisible by *p* itself

Make a checklist as shown below, to ease figuring out the conditions

**Case 1**

Consider number 1

Verify the numbers with given conditions,

Hence the number 1, is not a prime number

**Case 2**

Consider number 2

Verify the numbers with given conditions,

Hence the number 2, is a prime number

**Case 3**

Consider number 3

Verify the numbers with given conditions,

Hence the number 3, is a prime number

**Case 4**

Consider number 4

Verify the numbers with given conditions,

4 is divisible by not just 1 and 4, but also by 2.

In other words, 4 can be broken as a product of two natural numbers, 2 x 2.

Hence the number 4, is not a prime number

**Case 5**

Consider number 5

Verify the numbers with given conditions,

Hence the number 5, is a prime number

**Case 6**

Consider number 6

Verify the numbers with given conditions,

6 is divisible by not just 1 and 6, but also by 2 and 3.

In other words, 6 can be broken as a product of natural numbers, 2 x 3 and 3 x 2.

Hence the number 6, is not a prime number

**Case 7**

Consider number 7

Verify the numbers with given conditions,

Hence the number 7, is a prime number

*Prime Numbers *are kind of building blocks of numbers

Cannot break them down anymore.

Cannot break them into products of smaller natural numbers

Example in case 7. The number 7 cannot be broken down anymore,

in other words, 7 = seven times 1 or 1 time seven (1 x 7 or 7 x 1)

in this case, the number 7 could not be broken down further. It is noticed that 7 exists there again as seven times 1 or 1 time seven

This is the beauty of *Prime Numbers*

On the contrary lets us consider Case 4 and 6 which are not Prime in nature

Case 4. The number 4 can be broken down further, as a product of 2 x 2 apart from 1 x 4 and 4 x 1

Case 6. The number 6 can be broken down further, as a product of 2 x 3 apart from 1 x 6 and 6 x 1

In short, *Prime Numbers *cannot be drilled down.

Let us work with larger numbers

**Case 8**

Consider number 16

Verify the numbers with given conditions,

16 is divisible by not just 1 and 16, but also by 2, 4, and 8.

In other words, 16 can be broken as a product of natural numbers, 2 x 8, 4 x 4, 8 x 2.

Hence the number 16, is not a prime number

**Case 9**

Consider number 17

Verify the numbers with given conditions,

Hence the number 17, is a prime number

**Case 10**

Consider number 51

Verify the numbers with given conditions,

51 is divisible by not just 1 and 51, but also by 3.

In other words, 51 can be broken as a product of natural numbers, 3 x 17 and 17 x 3.

Hence the number 51, is not a prime number

**List/Chart/History(Background) of Prime Numbers**

Ancient Greek mathematicians were the first to extensively study *Prime Numbers* and their properties. The mathematicians of Pythagoras's school (500 BC to 300 BC) were interested in *Prime Numbers* for their mystical and numerological properties. They understood the idea of primality and were interested in perfect and amicable numbers.

In 300 BC, when Euclid's Elements appeared, several important results about *Prime Numbers* were proved. Euclid proof of the Fundamental Theorem of Arithmetic explains that “Every integer can be written as a product of *Prime Numbers* in an essentially unique way”.

In 200 BC, the Greek Eratosthenes devised an algorithm to calculate *Prime Numbers*, which in modern days is called the Sieve of Eratosthenes.

During the 17th Century, the next important developments in *Prime Numbers* were made by Fermat. Fermat's Little Theorem is the basis for many other results in Number Theory and is the basis for methods of checking whether numbers are prime which are still in use on today's electronic computers.

In 1952 the Mersenne numbers were proved to be prime by Robinson using an early computer and the electronic age had begun.

By 2018 a total of 50 Mersenne primes have been found.

Euler's work had a great impact on number theory in general and on *Prime Numbers* in particular.

### Twin Prime Numbers

Prime Numbers that differ by 2 are known as Twin Prime Numbers

For example, a list of Prime Numbers between 1 to 10 is displayed below,

Let us consider the first two Prime Numbers in the above number line.

It is 2 and 3.

The difference between 2 and 3 is 1 (3 - 2 = 1)

Hence, 2 and 3 are not Twin Prime Numbers

Let us consider the second pair of Prime Numbers in the given number line.

It is 3 and 5.

The difference between 3 and 5 is 2 (5 - 3 = 2)

Hence, 3 and 5 are Twin Prime Numbers

Similarly let us try with the third pair of Prime Numbers in the given number line.

It is 5 and 7.

The difference between 5 and 7 is 2 (7 - 3 = 2)

Hence, 5 and 7 are Twin Prime Numbers

As the numbers keep increasing in the number line, Prime Numbers become less frequent and Twin Prime Numbers become rare to be found in the series.

Co-Prime Numbers

Co-prime numbers are a set of numbers which have only 1 as their common factor. Co means two, and hence in order to identify Co-Prime Numbers we will be in need of two numbers.

For Example

Let us consider the pair of numbers 18 and 35.

18 can be broken or in other words can be written as product of two numbers as below,

1 x 18 = 18

2 x 9 = 18

3 x 6 = 18

6 x 3 = 18

9 x 2 = 18

18 x 1 = 18

From the above list of product of two numbers, the Factors of 18 are 1, 2, 3, 6, 9 and 18

Let us work out the same for number 35, which is the pairing number to 18 in the given statement.

35 can be broken or in other words can be written as product of two numbers as below,

1 x 35 = 35

5 x 7 = 35

7 x 5 = 35

35 x 1 = 35

From the above list of product of two numbers, the Factors of 35 are 1, 5, 7 and 35

Comparing the factors of 18 and 35, 1 appears to be the only common factor, thus satisfying the property of a pair of numbers to be termed as Co-Prime Numbers.

Let us work out for another set of numbers to identify the difference between Co-Prime Numbers and Non Co-Prime Numbers.

In this case, let us take 18 and 19

The outcome is as shown in the below image,

As the only common Factor for numbers 18 and 19 is 1, Numbers 18 and 19 can be termed as Co-Prime Numbers.

Another Example,

In this case, let us take 18 and 20

Though 1 is a common Factor for 18 and 20, yet there is another common Factor in the list which is number 2.

The Property of a Co-Prime Number is that it should have only 1 as the Common Factor. In this case, we also have 2 along with 1 as Common Factor and hence numbers 18 and 20 are not Co-Prime in nature.

Interesting fact about 1 is that it is a Co-Prime Number for all the numbers.

**Sieve of Eratosthenes**

It is an algorithm to find all given numbers up to a limit.

The algorithm to find prime numbers between 1- 100 proceeds like this.

**Step 1**

Make a table 0f 10 rows and 10 columns starting with 1 continuing until 100, as displayed in the below image

**Step 2**

Ignore number 1 and start with 2.

Based on the above illustrations it is evident that 2 is a prime number.

Mark 2 in the table as a prime number, by circling it

**Step 3**

Mark all the multiples of 2, this will help eliminate the composite numbers from the list thus highlighting only the primes step by step.

The multiple of 2 are marked in grey, to emphasize that the numbers which are not prime in nature are ignored.

**Step 4**

Now, find the smallest number in the list greater than 2 that is not marked, which will be the next prime number in the list. In this case, it is 3. Circle 3, and repeat step 3 to eliminate the multiples of 3.

**Step 5**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number, followed by will elimination of multiples of the prime number as per step 3

In this case, the next smallest number in the list is 5

**Step 6**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number, followed by will elimination of multiples of the prime number as per step 3

In this case, the next smallest number in the list is 7

**Step 7**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number, followed by will elimination of multiples of the prime number as per step 3

In this case, the next smallest number in the list is 11

**Step 8**

In this case, the next smallest number in the list is 13

**Step 9**

In this case, the next smallest number in the list is 17

**Step 10**

In this case, the next smallest number in the list is 19

**Step 11**

In this case, the next smallest number in the list is 23

**Step 12**

In this case, the next smallest number in the list is 29

**Step 13**

In this case, the next smallest number in the list is 31

**Step 14**

In this case, the next smallest number in the list is 37

**Step 15**

In this case, the next smallest number in the list is 41

**Step 16**

In this case, the next smallest number in the list is 43

**Step 17**

In this case, the next smallest number in the list is 47

**Step 18**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number.

In this case, the next smallest number in the list is 53

The elimination of multiples from this prime number may not be required as the table does not hold numbers greater than 100.

**Step 19**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number,

In this case, the next smallest number in the list is 59

**Step 20**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number,

In this case, the next smallest number in the list is 61

**Step 21**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number,

In this case, the next smallest number in the list is 67

**Step 22**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number,

In this case, the next smallest number in the list is 71

**Step 23**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number,

In this case, the next smallest number in the list is 73

**Step 24**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number,

In this case, the next smallest number in the list is 79

**Step 25**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number,

In this case, the next smallest number in the list is 83

**Step 26**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number,

In this case, the next smallest number in the list is 89

**Step 27**

Repeat Step 4 to find the next smallest number in the list which will be the next prime number,

In this case, the next smallest number in the list is 97

Based on the Sieve of Eratosthenes, the numbers that are classified as prime falling between 1 – 100 are, 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

**Frequently Asked Questions (FAQs)**

## What are co-prime numbers?

Pair of Numbers that have their greatest common divisor i.e. GCD is unity, which means that the only number that can divide each of them is 1.

## How to find prime numbers?

Prime Numbers can be found by using the Sieve of Eratosthenes.

## How many prime numbers are from 1-100?

There are 25 prime numbers from 1-100.

## What are twin prime numbers?

The pair of primes that differ by an amount of 2 are known as twin prime numbers.

## What is the sieve of Eratosthenes?

It is an algorithm to find all given numbers up to a limit.