Prime numbers and their properties were first studied extensively by the ancient Greek mathematicians.
The mathematicians of Pythagoras's school (500 BC to 300 BC) were interested in numbers for their mystical and numerological properties. They understood the idea of primality and were interested in perfect and amicable numbers.
A perfect number is one whose proper divisors sum to the number itself. e.g. The number 6 has proper divisors 1, 2 and 3 and 1 + 2 + 3 = 6, 28 has divisors 1, 2, 4, 7 and 14 and 1 + 2 + 4 + 7 + 14 = 28.
Fermat
By the time Euclid's Elements appeared in about 300 BC, several important results about primes had been proved. In Book IX of the Elements, Euclid proves that there are infinitely many prime numbers. This is one of the first proofs known which uses the method of contradiction to establish a result. Euclid also gives a proof of the Fundamental Theorem of Arithmetic: Every integer can be written as a product of primes in an essentially unique way.
Euclid also showed that if the number 2^n - 1 is prime then the number 2^n-1(2^n - 1) is a perfect number. The mathematician Euler (much later in 1747) was able to show that all even perfect numbers are of this form. It is not known to this day whether there are any odd perfect numbers.
In about 200 BC the Greek Eratosthenes devised an algorithm for calculating primes called the Sieve of Eratosthenes.
There is then a long gap in the history of prime numbers during what is usually called the Dark Ages.
The next important developments were made by Fermat at the beginning of the 17th Century. He proved a speculation of Albert Girard that every prime number of the form 4 n + 1 can be written in a unique way as the sum of two squares and was able to show how any number could be written as a sum of four squares.
He devised a new method of factorising large numbers which he demonstrated by factorising the number 2027651281 = 44021 * 46061.
He proved what has come to be known as Fermat's Little Theorem (to distinguish it from his so-called Last Theorem).
This states that if p is a prime then for any integer a we have a^p = a modulo p.
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.
Fermat corresponded with other mathematicians of his day and in particular with the monk Marin Mersenne. In one of his letters to Mersenne he conjectured that the numbers 2^n + 1 were always prime if n is a power of 2. He had verified this for n = 1, 2, 4, 8 and 16 and he knew that if n were not a power of 2, the result failed. Numbers of this form are called Fermat numbers and it was not until more than 100 years later that Euler showed that the next case 2^32 + 1 = 4294967297 is divisible by 641 and so is not prime.
Number of the form 2^n - 1 also attracted attention because it is easy to show that if unless n is prime these number must be composite. These are often called Mersenne numbers Mn because Mersenne studied them.
Not all numbers of the form 2^n - 1 with n prime are prime. For example 2^11 - 1 = 2047 = 23 * 89 is composite, though this was first noted as late as 1536.
For many years numbers of this form provided the largest known primes. The number M19 was proved to be prime by Cataldi in 1588 and this was the largest known prime for about 200 years until Euler proved that M31 is prime. This established the record for another century and when Lucas showed that M127 (which is a 39 digit number) is prime that took the record as far as the age of the electronic computer.
Lucas made important advance which, as modified by Lehmer in 1930, is the basis of computer searches used today to find Mersenne primes, and so to find perfect numbers.
In 1952 the Mersenne numbers M521, M607, M1279, M2203 and M2281 were proved to be prime by Robinson using an early computer and the electronic age had begun.
By 2009 a total of 46 Mersenne primes have been found. The largest is
Catalan-Mersenne Numbers:
Following the announcement by Lucas that p = 127 gave the Mersenne prime 2^p - 1, Catalan conjectured that, if m = 2^p - 1 is prime then 2^m - 1 is also prime.
Let C0 = 2, then let C1 = 2^C0-1, C2 = 2^C1-1, C3 = 2^C2-1, ... Are these all prime?
According to Dickson [Dickson v1p22] Catalan responded in 1876 to Lucas' stating 2^127-1 (C4) is prime with this sequence. These numbers grow very quickly:
C0 = 2 (prime)
C1 = 3 (prime)
C2 = 7 (prime)
C3 = 127 (prime)
C4 = 170141183460469231731687303715884105727 (prime)
C5 = 2^C4-1 (is C5 prime ? )
Are all Cn primes ???
Grand Mystery Alternative
Let C0=2, Cn+1=2^Cn - 1 ,0
It is easy to prove that there is alternative:
1.There are some integer number L there that for 0
and for n>=L, Cn—composites.
2. For all integer n ,0
If anyone reveals that conjuncture 1 led to contradiction it will be mean that statement 2 is true. It is illustrated in graphical form here.
Sierpinski W. Elementary theory of numbers (Warszawa, 1964)(L)(T)(224s).djvu
Shanks D. Solved and unsolved problems in number theory (1978)(L)(T)(145s).djvu
Apostol T.M. Introduction to analytic number theory (Springer, 1976)(T)(350s).djvu
Serr J.P. A course in arithmetic (Springer, 1996)(K)(T)(129s).djvu
More
Some Links
Simon Sing Fermat Corner
and
