The study of Prime numbers forms the basis of Number Theory.
A natural number is said to be Prime if it can be evenly divided by one and itself, for example: 2, 3, 5, 7, 11.The number 9 is not prime, as it can be divided by 3 other than 1 and 9. Prime numbers have only two distinct divisors, 1 and itself. The number which is not Prime is called Composite number.
There is no set formula to check the primality of the number, other than the definition itself. The most common algorithm to identify a prime number, is to start dividing the number by all odd numbers from 2(include it as an exception) up to its square root; if any divisor with zero remainder is found in the process then the number is Composite else Prime.
E.g. To check whether 53 is prime or not.
We’ll start dividing 53 with all odd numbers including two right up to the square root of 53 which is approximately 7; that is we’ll divide 53 by 2,3,5,7 and conclude 53 is prime.
The Greek Mathematician Eratosthenes has given an algorithm for finding Primes in a given range, called the Sieve of Eratosthenes. He used the elimination process, remove all the multiples of each number starting from 2.
To find all primes between 1 and 100.List all the numbers.
First eliminate all multiples of 2 i.e. 4,6,8,10,12,14 so on. Basically it eliminates all even numbers except 2.
Next eliminate all multiples of 3 i.e. 9,15,21 27 so on from the remaining numbers. Similarly multiples of 5 and 7 are eliminated.
The list of primes between 1 and 100 is
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
It is to be noted that, the natural number 1 is not Prime and 2 is the only even number which is Prime. Every even integer greater than 2 can be written as the sum of two Primes, states The Goldbach’s Conjecture, but has not yet been proved.
The fundamental theorem of arithmetic (or unique factorization theorem) states that every natural number greater than 1 can be written as a unique product of prime numbers. It is used to find the Greatest Common divisor (GCD) and the Least Common Multiple (LCM) in Elementary Arithmetic.
Prime numbers play an important role in data security in today’s information age. When we multiply two Prime numbers we get a composite number which is divisible by only those two Primes other than one and itself, which is quite obvious.
E.g. 3*5 = 15; where 3 &5 are Primes and the product 15 is composite
with factors 1,3,5 and 15.
The concept of product of two Prime numbers is a composite number with only two factors other than one and itself forms the basis of modern cryptography. The encryption and decryption of data, transmitted over the internet is done using the above concept. To find the product of two Primes is easy but the reverse that is, given a number and finding its two Prime factors is reasonably tedious even by fast computers, especially if the number is few hundred digits long, it may take couple of computing years.
Euclid has proved that the set of prime numbers is infinite. The pursuit for the largest prime number has always been a craze and fascination among mathematicians across the globe. The Largest Prime number till date is the 44th Mersenne Prime, 232,582,657-1. It is 9,808,358 digits long, discovered by Dr. Curtis Cooper and Dr. Steven Boone’s of Central Missouri State University, in Sept 2006. The Electronic Frontier Foundation has kept US$100,000 prize money for the discovery of a Prime with at least 10 million digits for which the quest is on.
