What are prime numbers?
Numbers were known to man since the beginning of history. It wasn�t very long that man discovered some numbers with strange properties. He discovered that numbers were divisible by other smaller numbers excluding 1. He called these numbers composite numbers. Then he found out that actually he was wrong! Not all numbers were composite. He made another category of numbers that were only divisible by themselves and 1. This is where the mysterious history of prime numbers began.
After the discovery of a prime number, people grew curious if there were more of them. They soon found the first primes�2,3,5,7,11,13,17,19,23,29,31,37,41�Then they wanted to know how many primes were there for them to solve. Nobody knew the answer up until the time of Euclid.
Euclid�s Proof of Infinitude of Primes
Euclid was a Greek mathematician that lived around 300 B.C. He proposed a theory that clearly showed that there were an infinite number of primes. The idea behind the theory was simple. Suppose that p1=2 and p2=3 and pr was the largest prime number. The inequality would be:
p1<p2<�< pr
If another number P equaled
P= (p1* p2*�* pr)+1
and let p be a divisor of P then p can not be any of p1, p2,�, pr, otherwise p would divide the difference P- (p1* p2*�* pr) which would equal 1, which is impossible. So p is another prime and p1, p2,�,pr would not be ALL of the primes. If you added p to the list of all the primes, again you would find another prime with the same method and so on and so forth until you find an infinite number of primes.
Although Euclid�s theory of infinitude of primes gave an insight of how many prime numbers there were, people still didn�t know an efficient method of finding prime numbers.
Sieve of Eratosthenes
Couple of decades after Euclid, another famous mathematician called Eratosthenes of Cyrene discovered a method of finding prime numbers up to a number n. First of all you write all the numbers up to n. Since 1 is neither a prime nor a composite number, set is as K. Until K exceeds or equals the square root of n, find the next number greater than K and call it m. Mark the numbers 2m,3m,4m� and cross them out because they are composite. After you are done with the entire list, call m a prime number and put it on your list of prime numbers. Then move to the next number that was not crossed out in the last round and call it m again and cross out 2m,3m.4m� until the end of the list. Follow this procedure until all the remaining numbers in your list are primes.
Fermat�s Discoveries
After Eratostenes, the history of prime numbers has a big gap which is caused by what we call the Dark Ages.
The mathematician Fermat reestablished the exploration of prime numbers in the 17th Century. Fermat proved that every prime number written in the form 4n+1 can be written in way as the sum of two squares. He also showed that any number could be written as a sum of 4 squares.
Fermat also devised a method of factorizing large numbers. This method was called �Fermat�s Little Theorem�. This stated that if p is a prime then for any integer a:
a^p=a (modulo p)
This theorem is useful today when checking whether a number is prime.
In one of Fermat�s letters to another mathematician called Mersenne, Fermat conjectured that any number in the form 2^n+1 is a prime if n is power of 2. He proved this conjecture using n=1,2,4,8 and 16. He knew that if n wasn�t a power of 2 then his theory wouldn�t work. He called this form of numbers Fermat Numbers and written as Fn. It wasn�t until 100 years later that Euler showed that the next Fermat Number 2^32+1= 4,294,967,297 which is divisible by 641, which proved that not all Fermat Numbers were prime.
Mersenne�s Discoveries
The form of the Fermat Numbers interested Mersenne. He devised his own numbers, but this time in the form 2^n-1. These numbers were easy to prove composite because if n wasn�t prime then 2^n-1 wouldn�t be prime either. These numbers were called Mersenne numbers and written in the form Mn.
Later it was founded that not all numbers in the form 2^n-1 with n=prime are prime. For example, 2^11-1=2047 which is 23*89. For many years Mersenne numbers proved to be the largest prime numbers. M19 was the largest prime number during Mersenne�s life. It was discovered by Cataldi. 200 years later Euler found that M31 is prime. Another 100 years later Lucas found that M127 is prime. In 1952, M521, M607, M1279, M2203 and M2281 were found to be prime using an electronic computer. By 2001, 39 Mersenne primes have been found. The largest one M13466917 has 4, 053,946 digits.Different Types of Primes
Primes are an entire different set of numbers. But even primes numbers have their own categories. Some of these categories are, Fermat primes, Mersenne primes, Twin primes, Palindrome primes and Factorial primes. Soon you will see that they all have their own properties.