Prime numbers: history and facts
The properties of prime numbers first began to study the mathematics of ancient Greece. The mathematicians of the Pythagorean school (500-300 BC) were primarily interested in the mystical and numerological properties of prime numbers. They were the first to come up with ideas about perfect and friendly numbers.
A perfect number has the sum of its own divisors equal to itself. For example, the intrinsic divisors of the number 6: 1, 2, and 3. 1 + 2 + 3 = 6. For the number 28, the divisors are 1, 2, 4, 7, and 14. At the same time, 1 + 2 + 4 + 7 + 14 = 28
Numbers are called friendly if the sum of the intrinsic divisors of one number is equal to another, and vice versa — for example, 220 and 284. We can say that the perfect number is friendly to itself.
')
By the time the Euclidean work "The Beginnings" appeared in 300 BC several important facts about prime numbers have already been proven. In book IX, "Beginning," Euclid proved that there are an infinite number of primes. This, by the way, is one of the first examples of using evidence from the contrary. He also proves the basic theorem of arithmetic - each integer can be represented uniquely as a product of prime numbers.
He also showed that if the number 2 n -1 is simple, then the number 2 n-1 * (2 n -1) will be perfect. Another mathematician, Euler, in 1747 was able to show that all even perfect numbers can be written in this form. To this day, it is not known whether odd perfect numbers exist.
In the year 200 BC. Greek Eratosthenes invented an algorithm for searching for primes called "Sieve of Eratosthenes."
And then there was a big break in the history of the study of prime numbers associated with the Middle Ages.
The following discoveries were already made at the beginning of the 17th century by the mathematician Fermat. He proved the hypothesis of Albert Girard that any simple number of the form 4n + 1 can be written uniquely as the sum of two squares, and also formulated the theorem that any number can be represented as the sum of four squares.
He developed a new method for factoring large numbers, and demonstrated it on the number 2027651281 = 44021 × 46061. He also proved the Fermat Minor Theorem: if p is a prime number, then for any integer a, a p = a modulo p will be true.
This statement proves half of what was known as the “Chinese hypothesis” and dates back 2000 years: the integer n is simple if and only if 2 n –2 is divisible by n. The second part of the hypothesis turned out to be false - for example, 2 341 - 2 divided by 341, although the number 341 is composite: 341 = 31 × 11.
Fermat's small theorem served as the basis for a multitude of other results in number theory and methods for testing numbers as belonging to simple ones - many of which are still used today.
The farm corresponded a lot with its contemporaries, especially with a monk named Maren Mersenn. In one of the letters, he expressed the hypothesis that numbers of the form 2 n +1 will always be simple if n is a power of two. He checked it for n = 1, 2, 4, 8 and 16, and was sure that in the case when n is not a power of two, the number is not necessarily simple. These numbers are called Fermat numbers, and only after 100 years, Euler showed that the next number, 2 32 + 1 = 4294967297, is divisible by 641, and therefore is not simple.
Numbers of the form 2 n - 1 were also the subject of research, since it is easy to show that if n is composite, then the number itself is also composite. These numbers are called Mersenne numbers, because he was actively studying them.
But not all numbers of the form 2 n - 1, where n is simple, are simple. For example, 2 11 - 1 = 2047 = 23 * 89. This was first discovered in 1536.
For many years, numbers of this kind have given mathematicians the greatest known prime numbers. That the number M is 19 , was proved by Cataldi in 1588, and for 200 years was the largest known prime, until Euler proved that M 31 is also simple. This record lasted another hundred years, and then Lukas showed that the M 127 is a simple one (and this is a number of 39 digits), and after it the research continued with the advent of computers.
In 1952, the simplicity of the numbers M 521 , M 607 , M 1279 , M 2203 and M 2281 was proved.
By 2005, 42 Mersenne primes were found. The largest of them, M 25964951 , consists of 7816230 digits.
Euler's work had a great influence on the theory of numbers, including simple ones. He expanded the Little Fermat theorem and introduced the φ-function. Factorized the 5th number of Farm 2 32 +1, found 60 pairs of amicable numbers, and formulated (but could not prove) the quadratic law of reciprocity.
He was the first to introduce the methods of mathematical analysis and developed an analytical theory of numbers. He proved that not only the harmonic series ∑ (1 / n), but also a series of
1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...
obtained by the sum of the inverse of the prime numbers, also diverges. The sum of the n terms of the harmonic series grows approximately as log (n), and the second row diverges more slowly, as log [log (n)]. This means that, for example, the sum of reciprocals to all the primes found so far will yield only 4, although the series still diverges.
At first glance, it seems that primes are distributed among integers rather randomly. For example, among the 100 numbers that go right before 10,000,000, there are 9 primes, and among the 100 numbers that go right after this value, only 2. But on large segments, prime numbers are distributed fairly evenly. Legendre and Gauss were concerned with their distribution. Gauss once told a friend that in any free 15 minutes he always counts the number of prime 1000 numbers. By the end of his life, he counted all the prime numbers in the interval to 3 million. Legendre and Gauss equally calculated that for large n the prime density is 1 / log (n). Legendre estimated the number of prime numbers in the range from 1 to n as
π (n) = n / (log (n) - 1.08366)
And Gauss - as a logarithmic integral
π (n) = ∫ 1 / log (t) dt
with an integration interval from 2 to n.
The statement about the density of prime numbers 1 / log (n) is known as the Theorem on the Distribution of Primes. She was tried to be proved throughout the 19th century, and Chebyshev and Riemann made progress. They connected it with the Riemann hypothesis - up to this time the unproven hypothesis about the distribution of the zeros of the Riemann zeta function. The density of prime numbers was simultaneously proved by Hadamard and Valle-Poussin in 1896.
In the theory of primes, there are still many unsolved questions, some of which have been around for hundreds of years:
The largest prime number calculated by the GIMPS project [Great Internet Mersenne Prime Search] can be viewed in the table on the official project page .
www.mersenne.org/primes
The biggest twins among the prime numbers are 2003663613 × 2 195000 ± 1. They consist of 58711 digits, and were found in 2007.
The largest factorial prime (of the form n! ± 1) is 147855! - 1. It consists of 142891 digits and was found in 2002.
The largest prime number (number n # ± 1) is 1098133 # + 1.
A perfect number has the sum of its own divisors equal to itself. For example, the intrinsic divisors of the number 6: 1, 2, and 3. 1 + 2 + 3 = 6. For the number 28, the divisors are 1, 2, 4, 7, and 14. At the same time, 1 + 2 + 4 + 7 + 14 = 28
Numbers are called friendly if the sum of the intrinsic divisors of one number is equal to another, and vice versa — for example, 220 and 284. We can say that the perfect number is friendly to itself.
')
By the time the Euclidean work "The Beginnings" appeared in 300 BC several important facts about prime numbers have already been proven. In book IX, "Beginning," Euclid proved that there are an infinite number of primes. This, by the way, is one of the first examples of using evidence from the contrary. He also proves the basic theorem of arithmetic - each integer can be represented uniquely as a product of prime numbers.
He also showed that if the number 2 n -1 is simple, then the number 2 n-1 * (2 n -1) will be perfect. Another mathematician, Euler, in 1747 was able to show that all even perfect numbers can be written in this form. To this day, it is not known whether odd perfect numbers exist.
In the year 200 BC. Greek Eratosthenes invented an algorithm for searching for primes called "Sieve of Eratosthenes."
And then there was a big break in the history of the study of prime numbers associated with the Middle Ages.
The following discoveries were already made at the beginning of the 17th century by the mathematician Fermat. He proved the hypothesis of Albert Girard that any simple number of the form 4n + 1 can be written uniquely as the sum of two squares, and also formulated the theorem that any number can be represented as the sum of four squares.
He developed a new method for factoring large numbers, and demonstrated it on the number 2027651281 = 44021 × 46061. He also proved the Fermat Minor Theorem: if p is a prime number, then for any integer a, a p = a modulo p will be true.
This statement proves half of what was known as the “Chinese hypothesis” and dates back 2000 years: the integer n is simple if and only if 2 n –2 is divisible by n. The second part of the hypothesis turned out to be false - for example, 2 341 - 2 divided by 341, although the number 341 is composite: 341 = 31 × 11.
Fermat's small theorem served as the basis for a multitude of other results in number theory and methods for testing numbers as belonging to simple ones - many of which are still used today.
The farm corresponded a lot with its contemporaries, especially with a monk named Maren Mersenn. In one of the letters, he expressed the hypothesis that numbers of the form 2 n +1 will always be simple if n is a power of two. He checked it for n = 1, 2, 4, 8 and 16, and was sure that in the case when n is not a power of two, the number is not necessarily simple. These numbers are called Fermat numbers, and only after 100 years, Euler showed that the next number, 2 32 + 1 = 4294967297, is divisible by 641, and therefore is not simple.
Numbers of the form 2 n - 1 were also the subject of research, since it is easy to show that if n is composite, then the number itself is also composite. These numbers are called Mersenne numbers, because he was actively studying them.
But not all numbers of the form 2 n - 1, where n is simple, are simple. For example, 2 11 - 1 = 2047 = 23 * 89. This was first discovered in 1536.
For many years, numbers of this kind have given mathematicians the greatest known prime numbers. That the number M is 19 , was proved by Cataldi in 1588, and for 200 years was the largest known prime, until Euler proved that M 31 is also simple. This record lasted another hundred years, and then Lukas showed that the M 127 is a simple one (and this is a number of 39 digits), and after it the research continued with the advent of computers.
In 1952, the simplicity of the numbers M 521 , M 607 , M 1279 , M 2203 and M 2281 was proved.
By 2005, 42 Mersenne primes were found. The largest of them, M 25964951 , consists of 7816230 digits.
Euler's work had a great influence on the theory of numbers, including simple ones. He expanded the Little Fermat theorem and introduced the φ-function. Factorized the 5th number of Farm 2 32 +1, found 60 pairs of amicable numbers, and formulated (but could not prove) the quadratic law of reciprocity.
He was the first to introduce the methods of mathematical analysis and developed an analytical theory of numbers. He proved that not only the harmonic series ∑ (1 / n), but also a series of
1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...
obtained by the sum of the inverse of the prime numbers, also diverges. The sum of the n terms of the harmonic series grows approximately as log (n), and the second row diverges more slowly, as log [log (n)]. This means that, for example, the sum of reciprocals to all the primes found so far will yield only 4, although the series still diverges.
At first glance, it seems that primes are distributed among integers rather randomly. For example, among the 100 numbers that go right before 10,000,000, there are 9 primes, and among the 100 numbers that go right after this value, only 2. But on large segments, prime numbers are distributed fairly evenly. Legendre and Gauss were concerned with their distribution. Gauss once told a friend that in any free 15 minutes he always counts the number of prime 1000 numbers. By the end of his life, he counted all the prime numbers in the interval to 3 million. Legendre and Gauss equally calculated that for large n the prime density is 1 / log (n). Legendre estimated the number of prime numbers in the range from 1 to n as
π (n) = n / (log (n) - 1.08366)
And Gauss - as a logarithmic integral
π (n) = ∫ 1 / log (t) dt
with an integration interval from 2 to n.
The statement about the density of prime numbers 1 / log (n) is known as the Theorem on the Distribution of Primes. She was tried to be proved throughout the 19th century, and Chebyshev and Riemann made progress. They connected it with the Riemann hypothesis - up to this time the unproven hypothesis about the distribution of the zeros of the Riemann zeta function. The density of prime numbers was simultaneously proved by Hadamard and Valle-Poussin in 1896.
In the theory of primes, there are still many unsolved questions, some of which have been around for hundreds of years:
- twin conjecture hypothesis - an infinite number of pairs of primes differing from each other by 2
- Goldbach hypothesis: any even number, starting with 4, can be represented as a sum of two prime numbers
- Is the number of primes of the form n 2 + 1 infinite?
- Is it always possible to find a prime number between n 2 and (n + 1) 2 ? (the fact that there is always a prime number between n and 2n was proved by Chebyshev)
- Is the number of farm numbers infinite? Are there any Fermat prime numbers after the 4th?
- Is there an arithmetic progression of consecutive primes for any given length? for example, for length 4: 251, 257, 263, 269. The maximum length found is 26 .
- Is the number of sets of three consecutive primes infinite in an arithmetic progression?
- n 2 - n + 41 is a prime number for 0 ≤ n ≤ 40. Are the numbers of such primes infinite? The same question for the formula n 2 - 79 n + 1601. These numbers are simple for 0 ≤ n ≤ 79.
- Is the number of primes of the form n # + 1 infinite? (n # is the result of multiplying all primes less than n)
- Is the number of primes of the form n # -1 infinite?
- Is there an infinite number of primes of the form n! + 1?
- Is there an infinite number of primes of the form n! - one?
- if p is simple, does 2 p -1 always contain no primes among the factors of the squares
- Does the Fibonacci sequence contain an infinite number of primes?
Current records among prime numbers
The largest prime number calculated by the GIMPS project [Great Internet Mersenne Prime Search] can be viewed in the table on the official project page .
www.mersenne.org/primes
The biggest twins among the prime numbers are 2003663613 × 2 195000 ± 1. They consist of 58711 digits, and were found in 2007.
The largest factorial prime (of the form n! ± 1) is 147855! - 1. It consists of 142891 digits and was found in 2002.
The largest prime number (number n # ± 1) is 1098133 # + 1.
Source: https://habr.com/ru/post/276037/
All Articles