Apparently, mathematicians of ancient Greece were first scientists who began studying prime numbers. Thus, mathematicians of Pythagorean school (500 - 300 BC) were interested primarily in the mystical and numerological properties of prime numbers. They first came to the idea of discovering perfect and amicable numbers. According to their hypotheses, a number can be considered as perfect if the sum of its proper divisors is equal to it. For example, the proper divisors of 6 are 1, 2 and 3. Consequently, 1 + 2 + 3 = 6. The same is true for 28, which proper divisors are 1, 2, 4, 7 and 14. Again, in this case, 1 + 2 + 4 + 7 + 14 = 28. Two numbers are called amicable if the sum of the own divisors of one of them is equal to that of the other, and vice versa - for example, this is true for 220 and 284. It can be said that a perfect number is always amicable to itself.
By the time the work ‘Elements’ by Euclid appeared in 300 BC several important facts about prime numbers had been already proven. In the book IX of ‘Elements’, Euclid proves that the list of prime numbers is infinite. This, incidentally, is one of the first examples of the use of reductio ad absurdum, or, in other words, a proof by contradiction. Euclid also proves in his book the main theorem of arithmetic: every integer can be uniquely represented as a product of primes. He also showed that if the number 2n-1 is simple, the number 2n-1 * (2n -1) will be perfect. Another mathematician, whose name was Euler, demonstrated in 1747 that all even perfect numbers can be written in this form. And it is not known to this very day whether there exist odd perfect numbers.
In the year 200 BC the Greek Eratosthenes came up with an algorithm for finding prime numbers called ‘Sieve of Eratosthenes’. And then there was a long break in the history of the study of prime numbers, which is associated, primarily, with the historical background of Middle Ages. The following discoveries were made in the early 17th century by the mathematician Fermat. He proved the hypothesis by Albert Girard that every prime of the form 4n + 1 can be written down in a unique way as a sum of two squares. Also, Fermat formulated a theorem according to which any number can be represented as the sum of four squares. He developed a new method of factoring large numbers and showed its appropriateness by the example of the number 2027651281 = 44021 × 46061. He famously was a father of Fermat's Little Theorem: if p is a prime, then it is true for any integer that [ap = a modulo p]. This statement proves a half of what is known as ‘the Chinese hypothesis’ and dates back to 2000 years earlier: a whole number n is prime if and only if 2n - 2 is divisible by n. The second part of the hypothesis was false: for example, 2341 - 2 is divisible by 341, while the number 341 is compound: 341 = 31 × 11. Many of Fermat’s findings still remain useful today such as Fermat’s Little Theorem that was a basis for many other results in the theory of numbers and the methods of verification for belonging of numbers to the list of prime numbers.
Fermat used to be in active correspondence with his contemporaries, especially the monk by the name of Marin Mersenne. In one of his letters Fermat conjectured that numbers of the form 2n + 1 will always be prime if n is a power of the number 2. He had checked the propriety of this hypothesis for n = 1, 2, 4, 8, 16 and was confident that when n is not a power of the number 2, the resulting number is not necessarily prime. Nowadays, these numbers are called Fermat numbers, although it was no sooner than in 100 years period that Euler had shown that the next number 232 + 1 = 4294967297 is divisible by 641, and therefore, is not prime. Numbers that appear in the form 2n - 1 were also the subject of investigations since it is easy to show that if n is a composite number, then the number itself is also a composite. These numbers are called Mersenne primes in honor of Marin Mersenne who studied them with great enthusiasm.
However, not all numbers, which appear in the form 2n – 1 (where n is a prime) belong to the list of prime numbers. For example, 211 – 1 = 2047 = 23 * 89. This was first discovered in the year 1536. For a long time, the numbers of this kind have been giving to mathematicians the largest known prime numbers. The number M19 was proven to be the largest prime by Cataldi in 1588 and it had been remaining so for 200 years until Euler proved that the M31 is also a prime number. This record lasted for a hundred years, and then Lucas showed that M127 is a prime too (and this number consists of 39 digits). Lucas was the last man who did the calculations by hand and after him, the study has continued with the advent of computers. In 1952, primality of the numbers M521, M607, M1279, M2203 and M2281 was proven. By 2016, mathematicians have found even more Mersenne primes, the largest of which, 274,207,281 – 1 consists of 22,338,618 digits.
Euler's work had an enormous influence on the theory of numbers, including the theory of primes. He extended Fermat's Little Theorem and introduced the φ-function. Also, he factorized the 5th Fermat number 232 + 1, found 60 pairs of amicable numbers, and formulated (but could not prove) quadratic reciprocity. In addition, he first introduced methods of mathematical analysis and developed an analytical theory of numbers. He proved that not only the harmonic series Σ (1/n) but a string of numbers received by summing the reciprocals to primes (such as 1/2 + 1/3 + 1/5 + 1/7 + 1/11 +...) diverges too. The sum of n members of a harmonic string of numbers grows approximately as log (n), whereas the second string diverges more slowly, as log [log (n)]. This means that, for example, the sum of the reciprocals of all those prime numbers already found gives a total of 4, although the string still diverges. One may think, at first glance, that prime numbers are distributed among whole ones quite by accident. For example, among 100 numbers which go no further than 10,000,000 one will meet 9 prime numbers, and among 100 numbers that go immediately after this value – just 2. However, prime numbers are distributed fairly evenly on large stretches. Thus, both Legendre and Gauss were very interested in the issue of their distribution. Gauss once told a friend that he always counted the number of primes in the next thousand of numbers in any spare 15 minutes. By the end of his life, he counted all the primes in the interval of up to 3 million. Legendre and Gauss have come to the same assumption that for large n’s the density of primes amounts to 1/log (n). Estimation of the size of the list of prime numbers is something Legendre was famous for, specifically in the range from 1 to n as π(n) = n/(log(n) - 1.08366). At the same time, the Gaussian integral was viewed as the logarithmic integral π (x) = ∫ 1/log(t) dt, with the integration interval from 2 to n. The statement about the density of primes 1/log(n) is known as the prime number theorem. There were numerous attempts to prove it during the 19th century, and Chebyshev together with Riemann achieved the sought solution. They connected the theorem to the Riemann hypothesis about the distribution of the Riemann zeta function zeros - the hypothesis which has not been proved to this very day. The density of primes was proved by both Hadamard and Vallée Poussin in the year 1896.
In the theory of prime numbers there are still many unresolved issues, some of which have been troubling the minds of scientists for hundreds of years, namely: