PRIME NUMBERS - FINDING THEM BY SIEVE OF ERATOSTHENES, TWIN PRIMES, CO-PRIMES

Please study Number Systems before Prime Numbers.
We introduced Natural Numbers there.

The branch of mathematics which deals with the
study of natural numbers, is called number theory.

The study of natural numbers which do not have any factors
(factors are the numbers which exactly divide with remainder zero)
other than 1 and itself, is a part of it.

They have been the subject of intense research in pure mathematics.

They have also found application outside of pure mathematics.
They formed the basis of the algorithms in public-key cryptography .

From  The fundamental theorem of arithmetic,  it is clear that
each natural number can be formed from the product of
these numbers, in a unique way.

These numbers are called Prime Numbers.

Definition of Prime Number

A natural number except 1, which does not have any factors other than 1 and itself is called a Prime Number or simply prime.

Examples :
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
are the primes below 50.

To see first 10,000 primes (the 10,000th is 104,729),
look at the List Of Primes.

Note :
(i) 1 is not a prime.
(ii) 2 is the only even prime.
(iii) There are only 4 single digit primes.

Composite Numbers

A number which has atleast one factor other than 1 and itself is called a Composite Number.

Examples :
4, 6, 8, 9, 12 etc. are composite numbers.

Note :
(i) Every composite number will have at least 3 factors.
(ii) 1 is not a composite number.
(iii) 9 is the only single digit odd composite number.
(iv) There are only 4 single digit composite numbers.

1 is neither a prime nor a composite number

Division of Natural Numbers into three disjoint sets

Thus we can divide the set of Natural Numbers into
three disjoint sets like (i) { 1 } (ii) { Prime Numbers }
(iii) { Composite Numbers }.

Method of finding Prime Numbers by Sieve of Eratosthenes

Eratosthenes was a Greek Mathematician, of 3rd century B.C.

He suggested a method to find out Prime Numbers.
It is called the SIEVE OF ERATOSTHENES.

This method helps to find out prime numbers
upto a given natural number n.

Let us see an Example.

Solved Example 1 of Prime Numbers :

Find out the Primes upto first 100 natural numbers
using the Sieve of Eratosthenes.

Solution:

STEP 1 :

Write all natural numbers from 1 to 100
in 10 rows of 10 numbers each.

STEP 2 :

Strike off 1 which is not a Prime.

STEP 3 :

First Prime is 2. Leave 2 and strike off
all the multiples of 2 which are 4, 6, 8..........100.

STEP 4 :

The next number that is left is 3
and 3 is a prime. Leave 3 and in the remaining numbers, strike off
all the multiples of 3 which are 9, 15, 21..........99.

STEP 5 :

The next number that is left is 5
and 5 is a prime.

Leave 5 and in the remaining numbers, strike off
all the multiples of 5 which are 25, 35, 55..........95.

STEP 6 :

The next number that is left is 7
and 7 is a prime.

Leave 7 and in the remaining numbers, strike off
all the multiples of 7 which are 49, 77, 91.

STEP 7 :

This process will end at this stage.

Observe all the remaining numbers are primes only.

Note that, for finding primes upto 100,
7 is the highest prime which does not exceed √100 (= 10).

So the process ended after striking off multiples of 7.

In general

For finding primes upto n,
We have to continue this process upto
the highest prime which does not exceed √n.

Method of finding Prime Numbers by Formulas

Formulating the set of primes is far from easy.

There are several attempts to arrive at formulae for Prime Numbers.
Some of them use concepts of advanced mathematics.

Here is a simple one.

Euler's Formula

Euler's formula states that the quadratic polynomial
n² + n + 41
is a prime number for all non-negative integers less than 40.

The primes for n = 0, 1, 2, 3... are 41, 43, 47, 53, 61, 71...

The differences between the terms are 2, 4, 6, 8, 10...

For n = 40, it produces a square number, 1681,
which is equal to 41×41,
the smallest composite number for this formula.

Fermat's Formula

Fermat proposed that the numbers of the form
2²ⁿ + 1 are primes.

But it is true, when n = 0, 1, 2, 3 and 4
and the corresponding Primes,
called Fermat's Primes are 3, 5, 17, 257, 65537.

Euler proved that when n = 5, 2²⁵ + 1 is a Composite Number.

Set of prime Numbers is Infinite

When we observe the set of primes,
the composite numbers between any two primes
is continuosly increasing.

Look at the  List of Primes.
We observe that there are a mere 80 primes
between 103,000 and 104,000.

It is suspected that the process of getting
a prime may cease at any stage.

But Euclid proved that the set of Primes is infinite.

Scientists are finding larger and larger Primes
using Super Computers.

Primes having more than nine million digits were also found.

Twin Primes

A pair of primes are said to be twin primes if they differ by 2.

Examples :
3 and 5 are primes and they differ by 2.
So 3, 5 are twin primes.

Similarly 5 and 7 are twin primes.

17 and 19, 29 and 31, 71 and 73 are some more examples.

A question arises : Are there infinitely many twin primes ?
This is still an unsolved problem in number theory.

To see more about twin primes and other types of primes
go to the  List Of Primes.

Relatively Prime Numbers
or Co-Prime Numbers

Two natural numbers which do not have a common factor
other than 1 are relatively prime to each other and are called
co-prime numbers or simply co-primes..

Examples :
(2, 3), (2, 5), (2, 7), (2, 9), (2, 11), ............
(3, 4), (3, 5), (3, 7), (3, 8), (3, 10), ............
(4, 5), (4, 7), (4, 9), (4, 11), (4, 13), ............
(5, 6), (5, 7), (5, 8), (5, 9), (5, 11), ............
(6, 7), (6, 11), (6, 13), (6, 17), (6, 19), ............
............................................................
are pairs of co-primes.

NOTE :

(1) The  G.C.F.  of two relatively primes is 1
and their  L.C.M.  is the product of the numbers.

(2) Any two primes are always relatively prime to each other.

(3) Two relatively prime numbers need not be primes.
See the pair (4, 9). Neither 4 nor 9 is a prime number.
But, they are relatively prime to each other.

(4) We can observe that,

If two co-primes are factors of a number, their product is also a factor of the number.

(5) We can also observe that,

If a and b are co-primes, c is another number such that, a is a factor of bc, then a is a factor of c.

(6) The integer 1 is coprime to every natural number, including itself.

Prime Factors and Prime Factorization

The factors of a number which are prime numbers are called the Prime Factors of that number.

Expressing a given number as the product of Prime Factors is called Prime Factorization.

For knowing more about these, see Prime Factorization.