In this article we will explore prime and composite numbers. First, we will give definitions of prime and composite numbers, and also give examples. After this we will prove that there are infinitely many prime numbers. Next, we will write down a table of prime numbers, and consider methods for compiling a table of prime numbers, paying particular attention to the method called the sieve of Eratosthenes. In conclusion, we will highlight the main points that need to be taken into account when proving that a given number is prime or composite.
Page navigation.
Prime and Composite Numbers - Definitions and Examples
The concepts of prime numbers and composite numbers refer to numbers that are greater than one. Such integers, depending on the number of their positive divisors, are divided into prime and composite numbers. So to understand definitions of prime and composite numbers, you need to have a good understanding of what divisors and multiples are.
Definition.
Prime numbers are integers, large units, that have only two positive divisors, namely themselves and 1.
Definition.
Composite numbers are integers, large ones, that have at least three positive divisors.
Separately, we note that the number 1 does not apply to either prime or composite numbers. Unit has only one positive divisor, which is the number 1 itself. This distinguishes the number 1 from all other positive integers that have at least two positive divisors.
Considering that positive integers are , and that one has only one positive divisor, we can give other formulations of the stated definitions of prime and composite numbers.
Definition.
Prime numbers are natural numbers that have only two positive divisors.
Definition.
Composite numbers are natural numbers that have more than two positive divisors.
Note that every positive integer greater than one is either a prime or a composite number. In other words, there is not a single integer that is neither prime nor composite. This follows from the property of divisibility, which states that the numbers 1 and a are always divisors of any integer a.
Based on the information in the previous paragraph, we can give the following definition of composite numbers.
Definition.
Natural numbers that are not prime are called composite.
Let's give examples of prime and composite numbers.
Examples of composite numbers include 6, 63, 121, and 6,697. This statement also needs clarification. The number 6, in addition to positive divisors 1 and 6, also has divisors 2 and 3, since 6 = 2 3, therefore 6 is truly a composite number. Positive factors of 63 are the numbers 1, 3, 7, 9, 21 and 63. The number 121 is equal to the product 11·11, so its positive divisors are 1, 11 and 121. And the number 6,697 is composite, since its positive divisors, in addition to 1 and 6,697, are also the numbers 37 and 181.
In conclusion of this point, I would also like to draw attention to the fact that prime numbers and coprime numbers are far from the same thing.
Prime numbers table
Prime numbers, for the convenience of their further use, are recorded in a table called a table of prime numbers. Below is prime numbers table up to 1,000.
A logical question arises: “Why did we fill the table of prime numbers only up to 1,000, isn’t it possible to create a table of all existing prime numbers”?
Let's answer the first part of this question first. For most problems that require the use of prime numbers, prime numbers within a thousand will be sufficient. In other cases, most likely, you will have to resort to some special solutions. Although we can certainly create a table of prime numbers up to an arbitrarily large finite positive integer, be it 10,000 or 1,000,000,000, in the next paragraph we will talk about methods for creating tables of prime numbers, in particular, we will look at a method called.
Now let's look at the possibility (or rather, the impossibility) of compiling a table of all existing prime numbers. We cannot make a table of all the prime numbers because there are infinitely many prime numbers. The last statement is a theorem that we will prove after the following auxiliary theorem.
Theorem.
The smallest positive divisor other than 1 of a natural number greater than one is a prime number.
Proof.
Let a is a natural number greater than one, and b is the smallest positive divisor of a other than one. Let us prove that b is a prime number by contradiction.
Let's assume that b is a composite number. Then there is a divisor of the number b (let's denote it b 1), which is different from both 1 and b. If we also take into account that the absolute value of the divisor does not exceed the absolute value of the dividend (we know this from the properties of divisibility), then condition 1 must be satisfied
Since the number a is divisible by b according to the condition, and we said that b is divisible by b 1, the concept of divisibility allows us to talk about the existence of integers q and q 1 such that a=b q and b=b 1 q 1 , from where a= b 1 ·(q 1 ·q) . It follows that the product of two integers is an integer, then the equality a=b 1 ·(q 1 ·q) indicates that b 1 is a divisor of the number a. Taking into account the above inequalities 1
Now we can prove that there are infinitely many prime numbers.
Theorem.
There are an infinite number of prime numbers.
Proof.
Let's assume that this is not the case. That is, suppose that there are only n prime numbers, and these prime numbers are p 1, p 2, ..., p n. Let us show that we can always find a prime number different from those indicated.
Consider the number p equal to p 1 ·p 2 ·…·p n +1. It is clear that this number is different from each of the prime numbers p 1, p 2, ..., p n. If the number p is prime, then the theorem is proven. If this number is composite, then by virtue of the previous theorem there is a prime divisor of this number (we denote it p n+1). Let us show that this divisor does not coincide with any of the numbers p 1, p 2, ..., p n.
If this were not so, then, according to the properties of divisibility, the product p 1 ·p 2 ·…·p n would be divided by p n+1. But the number p is also divisible by p n+1, equal to the sum p 1 ·p 2 ·…·p n +1. It follows that p n+1 must divide the second term of this sum, which is equal to one, but this is impossible.
Thus, it has been proven that a new prime number can always be found that is not included among any number of predetermined prime numbers. Therefore, there are infinitely many prime numbers.
So, due to the fact that there are an infinite number of prime numbers, when compiling tables of prime numbers, you always limit yourself from above to some number, usually 100, 1,000, 10,000, etc.
Sieve of Eratosthenes
Now we will discuss ways to create tables of prime numbers. Suppose we need to make a table of prime numbers up to 100.
The most obvious method for solving this problem is to sequentially check positive integers, starting from 2 and ending with 100, for the presence of a positive divisor that is greater than 1 and less than the number being tested (from the properties of divisibility we know that the absolute value of the divisor does not exceed the absolute value of the dividend, non-zero). If such a divisor is not found, then the number being tested is prime, and it is entered into the prime numbers table. If such a divisor is found, then the number being tested is composite; it is NOT entered in the table of prime numbers. After this, there is a transition to the next number, which is similarly checked for the presence of a divisor.
Let's describe the first few steps.
We start with the number 2. The number 2 has no positive divisors other than 1 and 2. Therefore, it is simple, therefore, we enter it in the table of prime numbers. Here it should be said that 2 is the smallest prime number. Let's move on to number 3. Its possible positive divisor other than 1 and 3 is the number 2. But 3 is not divisible by 2, therefore, 3 is a prime number, and it also needs to be included in the table of prime numbers. Let's move on to number 4. Its positive divisors other than 1 and 4 can be the numbers 2 and 3, let's check them. The number 4 is divisible by 2, therefore, 4 is a composite number and does not need to be included in the table of prime numbers. Please note that 4 is the smallest composite number. Let's move on to number 5. We check whether at least one of the numbers 2, 3, 4 is its divisor. Since 5 is not divisible by 2, 3, or 4, then it is prime, and it must be written down in the table of prime numbers. Then there is a transition to the numbers 6, 7, and so on up to 100.
This approach to compiling a table of prime numbers is far from ideal. One way or another, he has a right to exist. Note that with this method of constructing a table of integers, you can use divisibility criteria, which will slightly speed up the process of finding divisors.
There is a more convenient way to create a table of prime numbers, called. The word “sieve” present in the name is not accidental, since the actions of this method help, as it were, to “sift” whole numbers and large units through the sieve of Eratosthenes in order to separate simple ones from composite ones.
Let's show the sieve of Eratosthenes in action when compiling a table of prime numbers up to 50.
First, write down the numbers 2, 3, 4, ..., 50 in order.
The first number written, 2, is prime. Now, from number 2, we sequentially move to the right by two numbers and cross out these numbers until we reach the end of the table of numbers being compiled. This will cross out all numbers that are multiples of two.
The first number following 2 that is not crossed out is 3. This number is prime. Now, from number 3, we sequentially move to the right by three numbers (taking into account the already crossed out numbers) and cross them out. This will cross out all numbers that are multiples of three.
The first number following 3 that is not crossed out is 5. This number is prime. Now from the number 5 we consistently move to the right by 5 numbers (we also take into account the numbers crossed out earlier) and cross them out. This will cross out all numbers that are multiples of five.
Next, we cross out numbers that are multiples of 7, then multiples of 11, and so on. The process ends when there are no more numbers to cross off. Below is the completed table of prime numbers up to 50, obtained using the sieve of Eratosthenes. All uncrossed numbers are prime, and all crossed out numbers are composite.
Let's also formulate and prove a theorem that will speed up the process of compiling a table of prime numbers using the sieve of Eratosthenes.
Theorem.
The smallest positive divisor of a composite number a that is different from one does not exceed , where is from a .
Proof.
Let us denote by the letter b the smallest divisor of a composite number a that is different from one (the number b is prime, as follows from the theorem proven at the very beginning of the previous paragraph). Then there is an integer q such that a=b·q (here q is a positive integer, which follows from the rules of multiplication of integers), and (for b>q the condition that b is the least divisor of a is violated, since q is also a divisor of the number a due to the equality a=q·b ). By multiplying both sides of the inequality by a positive and an integer greater than one (we are allowed to do this), we obtain , from which and .
What does the proven theorem give us regarding the sieve of Eratosthenes?
Firstly, crossing out composite numbers that are multiples of a prime number b should begin with a number equal to (this follows from the inequality). For example, crossing out numbers that are multiples of two should begin with the number 4, multiples of three with the number 9, multiples of five with the number 25, and so on.
Secondly, compiling a table of prime numbers up to the number n using the sieve of Eratosthenes can be considered complete when all composite numbers that are multiples of prime numbers not exceeding . In our example, n=50 (since we are making a table of prime numbers up to 50) and, therefore, the sieve of Eratosthenes should eliminate all composite numbers that are multiples of the prime numbers 2, 3, 5 and 7 that do not exceed the arithmetic square root of 50. That is, we no longer need to search for and cross out numbers that are multiples of prime numbers 11, 13, 17, 19, 23 and so on up to 47, since they will already be crossed out as multiples of smaller prime numbers 2, 3, 5 and 7 .
Is this number prime or composite?
Some tasks require finding out whether a given number is prime or composite. In general, this task is far from simple, especially for numbers whose writing consists of a significant number of characters. In most cases, you have to look for some specific way to solve it. However, we will try to give direction to the train of thought for simple cases.
Of course, you can try to use divisibility tests to prove that a given number is composite. If, for example, some test of divisibility shows that a given number is divisible by some positive integer greater than one, then the original number is composite.
Example.
Prove that 898,989,898,989,898,989 is a composite number.
Solution.
The sum of the digits of this number is 9·8+9·9=9·17. Since the number equal to 9·17 is divisible by 9, then by divisibility by 9 we can say that the original number is also divisible by 9. Therefore, it is composite.
A significant drawback of this approach is that the divisibility criteria do not allow one to prove the primeness of a number. Therefore, when testing a number to see whether it is prime or composite, you need to proceed differently.
The most logical approach is to try all possible divisors of a given number. If none of the possible divisors is a true divisor of a given number, then this number will be prime, otherwise it will be composite. From the theorems proved in the previous paragraph, it follows that divisors of a given number a must be sought among prime numbers not exceeding . Thus, a given number a can be sequentially divided by prime numbers (which are conveniently taken from the table of prime numbers), trying to find the divisor of the number a. If a divisor is found, then the number a is composite. If among the prime numbers not exceeding , there is no divisor of the number a, then the number a is prime.
Example.
Number 11 723 simple or compound?
Solution.
Let's find out up to what prime number the divisors of the number 11,723 can be. To do this, let's evaluate.
It's pretty obvious that 
, since 200 2 =40,000, and 11,723<40 000
(при необходимости смотрите статью comparison of numbers). Thus, the possible prime factors of 11,723 are less than 200. This already makes our task much easier. If we didn’t know this, then we would have to go through all the prime numbers not up to 200, but up to the number 11,723.
If desired, you can evaluate more accurately. Since 108 2 =11,664, and 109 2 =11,881, then 108 2<11 723<109 2
, следовательно, 
. Thus, any of the prime numbers less than 109 is potentially a prime factor of the given number 11,723.
Now we will sequentially divide the number 11,723 into prime numbers 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 , 101 , 103 , 107 . If the number 11,723 is divided by one of the written prime numbers, then it will be composite. If it is not divisible by any of the written prime numbers, then the original number is prime.
We will not describe this whole monotonous and monotonous process of division. Let's say right away that 11,723
Prime number is a natural (positive integer) number that is divisible without a remainder by only two natural numbers: by and by itself. In other words, a prime number has exactly two natural divisors: and the number itself.
By definition, the set of all divisors of a prime number is two-element, i.e. represents a set.
The set of all prime numbers is denoted by the symbol. Thus, due to the definition of the set of prime numbers, we can write: .
The sequence of prime numbers looks like this:
Fundamental Theorem of Arithmetic
Fundamental Theorem of Arithmetic states that every natural number greater than one can be represented as a product of prime numbers, and in a unique way, up to the order of the factors. Thus, prime numbers are the elementary "building blocks" of the set of natural numbers.
Natural number expansion title="Rendered by QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} canonical:
where is a prime number, and . For example, the canonical expansion of a natural number looks like this: .
Representing a natural number as a product of primes is also called factorization of a number.
Properties of Prime Numbers
Sieve of Eratosthenes
One of the most famous algorithms for searching and recognizing prime numbers is sieve of Eratosthenes. So this algorithm was named after the Greek mathematician Eratosthenes of Cyrene, who is considered the author of the algorithm.
To find all prime numbers less than a given number, following the method of Eratosthenes, the following steps must be followed:
Step 1. Write down all the natural numbers from two to , i.e. .
Step 2. Assign the variable the value , that is, the value equal to the smallest prime number.
Step 3. Cross out in the list all numbers from to that are multiples of , that is, the numbers: .
Step 4. Find the first uncrossed number in the list greater than , and assign the value of this number to a variable.
Step 5. Repeat steps 3 and 4 until number is reached.
The process of applying the algorithm will look like this:
All remaining uncrossed numbers in the list at the end of the process of applying the algorithm will be the set of prime numbers from to .
Goldbach conjecture
Cover of the book “Uncle Petros and the Goldbach Hypothesis”
Despite the fact that prime numbers have been studied by mathematicians for quite a long time, many related problems remain unsolved today. One of the most famous unsolved problems is Goldbach's hypothesis, which is formulated as follows:
- Is it true that every even number greater than two can be represented as the sum of two prime numbers (Binary Goldbach Hypothesis)?
- Is it true that every odd number greater than 5 can be represented as the sum of three prime numbers (Goldbach's ternary hypothesis)?
It should be said that the ternary Goldbach hypothesis is a special case of the binary Goldbach hypothesis, or as mathematicians say, the ternary Goldbach hypothesis is weaker than the binary Goldbach hypothesis.
Goldbach's conjecture became widely known outside the mathematical community in 2000 thanks to a promotional marketing stunt by the publishing companies Bloomsbury USA (USA) and Faber and Faber (UK). These publishing houses, having released the book “Uncle Petros and Goldbach’s Conjecture,” promised to pay a prize of 1 million US dollars to anyone who proves Goldbach’s hypothesis within 2 years from the date of publication of the book. Sometimes the mentioned prize from publishers is confused with prizes for solving the Millennium Prize Problems. Make no mistake, Goldbach’s hypothesis is not classified by the Clay Institute as a “millennium challenge,” although it is closely related to Riemann hypothesis- one of the “millennium challenges”.
The book “Prime numbers. Long road to infinity"
Cover of the book “The World of Mathematics. Prime numbers. Long road to infinity"
Additionally, I recommend reading a fascinating popular science book, the annotation to which says: “The search for prime numbers is one of the most paradoxical problems in mathematics. Scientists have been trying to solve it for several millennia, but, growing with new versions and hypotheses, this mystery still remains unsolved. The appearance of prime numbers is not subject to any system: they appear spontaneously in the series of natural numbers, ignoring all attempts by mathematicians to identify patterns in their sequence. This book will allow the reader to trace the evolution of scientific concepts from ancient times to the present day and introduce the most interesting theories of searching for prime numbers.”
Additionally, I will quote the beginning of the second chapter of this book: “Prime numbers are one of the important topics that return us to the very origins of mathematics, and then, along a path of increasing complexity, lead us to the forefront of modern science. Thus, it would be very useful to trace the fascinating and complex history of prime number theory: exactly how it developed, exactly how the facts and truths that are now generally accepted were collected. In this chapter we will see how generations of mathematicians carefully studied the natural numbers in search of a rule that predicted the appearance of prime numbers - a rule that became increasingly elusive as the search progressed. We will also look in detail at the historical context: the conditions under which mathematicians worked and the extent to which their work involved mystical and semi-religious practices, which are quite different from the scientific methods used in our time. Nevertheless, slowly and with difficulty, the ground was prepared for new views that inspired Fermat and Euler in the 17th and 18th centuries.”
A prime number is a natural number that is divisible only by itself and one.
The remaining numbers are called composite numbers.
Prime natural numbers
But not all natural numbers are prime numbers.
Prime natural numbers are only those that are divisible only by themselves and one.
Examples of prime numbers:
2; 3; 5; 7; 11; 13;...
Prime Integers
It follows that only natural numbers are prime numbers.
This means that prime numbers are necessarily natural numbers.
But all natural numbers are also integers.
Thus, all prime numbers are integers.
Examples of prime numbers:
2; 3; 5; 7; 11; 13; 17; 19; 23;...
Even prime numbers
There is only one even prime number - the number two.
All other prime numbers are odd.
Why can't an even number greater than two be a prime number?
But because any even number greater than two will be divisible by itself, not by one and by two, that is, such a number will always have three divisors, and possibly more.
- Translation
The properties of prime numbers were first studied by mathematicians of Ancient Greece. 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 a sum of its own divisors equal to itself. For example, the proper divisors of the number 6 are 1, 2 and 3. 1 + 2 + 3 = 6. The divisors of the number 28 are 1, 2, 4, 7 and 14. Moreover, 1 + 2 + 4 + 7 + 14 = 28.
Numbers are called friendly if the sum of the proper divisors of one number is equal to another, and vice versa - for example, 220 and 284. We can say that a perfect number is friendly to itself.
By the time of Euclid's Elements in 300 B.C. Several important facts about prime numbers have already been proven. In Book IX of the Elements, Euclid proved that there are an infinite number of prime numbers. This, by the way, is one of the first examples of using proof by contradiction. He also proves the Fundamental Theorem of Arithmetic - every integer can be represented uniquely as a product of prime numbers.
He also showed that if the number 2n-1 is prime, then the number 2n-1 * (2n-1) will be perfect. Another mathematician, Euler, was able to show in 1747 that all even perfect numbers can be written in this form. To this day it is unknown whether odd perfect numbers exist.
In the year 200 BC. The Greek Eratosthenes came up with an algorithm for finding prime numbers called the 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 made already at the beginning of the 17th century by the mathematician Fermat. He proved Albert Girard's conjecture that any prime 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 written 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 Fermat's Little Theorem: if p is a prime number, then for any integer a it will be true that a p = a modulo p.
This statement proves half of what was known as the "Chinese conjecture" and dates back 2000 years: an integer n is prime 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 is divisible by 341, although the number 341 is composite: 341 = 31 × 11.
Fermat's Little Theorem served as the basis for many other results in number theory and methods for testing whether numbers are primes - many of which are still used today.
Fermat corresponded a lot with his contemporaries, especially with a monk named Maren Mersenne. In one of his letters, he hypothesized that numbers of the form 2 n +1 will always be prime if n is a power of two. He tested this for n = 1, 2, 4, 8 and 16, and was confident that in the case where n was not a power of two, the number was not necessarily prime. These numbers are called Fermat's numbers, and only 100 years later Euler showed that the next number, 2 32 + 1 = 4294967297, is divisible by 641, and therefore is not prime.
Numbers of the form 2 n - 1 have also been 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 studied them extensively.
But not all numbers of the form 2 n - 1, where n is prime, are prime. For example, 2 11 - 1 = 2047 = 23 * 89. This was first discovered in 1536.
For many years, numbers of this kind provided mathematicians with the largest known prime numbers. That M 19 was proven by Cataldi in 1588, and for 200 years was the largest known prime number, until Euler proved that M 31 was also prime. This record stood for another hundred years, and then Lucas showed that M 127 is prime (and this is already a number of 39 digits), and after that research continued with the advent of computers.
In 1952, the primeness of the numbers M 521, M 607, M 1279, M 2203 and M 2281 was proven.
By 2005, 42 Mersenne primes had been found. The largest of them, M 25964951, consists of 7816230 digits.
Euler's work had a huge impact on the theory of numbers, including prime numbers. He extended Fermat's Little Theorem and introduced the φ-function. Factorized the 5th Fermat number 2 32 +1, found 60 pairs of friendly numbers, and formulated (but could not prove) the quadratic reciprocity law.
He was the first to introduce methods of mathematical analysis and develop analytical number theory. He proved that not only the harmonic series ∑ (1/n), but also a series of the form
1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…
The result obtained by the sum of the reciprocals of prime numbers also diverges. The sum of n terms of the harmonic series grows approximately as log(n), and the second series diverges more slowly as log[ log(n) ]. This means that, for example, the sum of the reciprocals of all prime numbers found to date will give only 4, although the series still diverges.
At first glance, it seems that prime numbers are distributed quite randomly among integers. For example, among the 100 numbers immediately before 10000000 there are 9 primes, and among the 100 numbers immediately after this value there are only 2. But over large segments the prime numbers are distributed quite evenly. Legendre and Gauss dealt with issues of their distribution. Gauss once told a friend that in any free 15 minutes he always counts the number of primes in the next 1000 numbers. By the end of his life, he had counted all the prime numbers up 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 is like a logarithmic integral
π(n) = ∫ 1/log(t) dt
With an integration interval from 2 to n.
The statement about the density of primes 1/log(n) is known as the Prime Distribution Theorem. They tried to prove it throughout the 19th century, and progress was achieved by Chebyshev and Riemann. They connected it with the Riemann hypothesis, a still unproven hypothesis about the distribution of zeros of the Riemann zeta function. The density of prime numbers was simultaneously proved by Hadamard and Vallée-Poussin in 1896.
There are still many unsolved questions in prime number theory, some of which are hundreds of years old:
- The twin prime hypothesis is about an infinite number of pairs of prime numbers that differ from each other by 2
- Goldbach's conjecture: any even number, starting with 4, can be represented as the sum of two prime numbers
- Is there an infinite number of prime numbers of the form n 2 + 1?
- 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 proven by Chebyshev)
- Is the number of Fermat primes infinite? Are there any Fermat primes after 4?
- 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 there an infinite number of sets of three consecutive prime numbers in an arithmetic progression?
- n 2 - n + 41 is a prime number for 0 ≤ n ≤ 40. Is there an infinite number of such prime numbers? The same question for the formula n 2 - 79 n + 1601. These numbers are prime for 0 ≤ n ≤ 79.
- Is there an infinite number of prime numbers of the form n# + 1? (n# is the result of multiplying all prime numbers less than n)
- Is there an infinite number of prime numbers of the form n# -1 ?
- Is there an infinite number of prime numbers of the form n? + 1?
- Is there an infinite number of prime numbers of the form n? - 1?
- if p is prime, does 2 p -1 always not contain prime squares among its factors?
- does the Fibonacci sequence contain an infinite number of prime numbers?
The largest twin prime numbers are 2003663613 × 2 195000 ± 1. They consist of 58711 digits and were discovered in 2007.
The largest factorial prime number (of the type n! ± 1) is 147855! - 1. It consists of 142891 digits and was found in 2002.
The largest primorial prime number (a number of the form n# ± 1) is 1098133# + 1.
Tags: Add tags
How this observation was made is colorfully described by M. Gardner in “Mathematical Leisure” (M., “Mir”, 1972). Here is this piece (p. 413417):
Depending on the arrangement of integers, prime numbers can form one pattern or another. Once upon a time, the mathematician Stanislaw M. Ulam had to attend a very long and, in his words, very boring report. To have some fun, he drew vertical and horizontal lines on a piece of paper and was about to start making chess studies, but then he changed his mind and began numbering the intersections, putting 1 in the center and moving in a counterclockwise spiral. Without any second thought, he circled all the prime numbers. Soon, to his surprise, the circles began to line up along straight lines with amazing tenacity. In Fig. 203 shows what a spiral with the first hundred numbers (from 1 to 100) looked like. [ This is a two-turn version of Figure 1 above, so I am not including it here. ? E.G.A.] For convenience, the numbers are inscribed in cells and do not stand at the intersection of lines.
Near the center, the alignment of prime numbers along straight lines could still be expected, since the density of prime numbers is initially large and all of them, except for the number 2, are odd. If the squares of a chessboard are numbered in a spiral, then all odd numbers will end up on squares of the same color. Taking 17 pawns (corresponding to 17 prime numbers not exceeding the number 64) and placing them at random on squares of the same color, you will find that the pawns are lined up along diagonal lines. However, there was no reason to expect that in the region of large numbers, where the density of prime numbers is much less, they would also line up along straight lines. Ulam became interested in what his spiral would look like if it were extended to several thousand prime numbers.
In the computing department of the Los Alamos Laboratory, where Ulam worked, there was a magnetic tape on which 90 million prime numbers were recorded. Ulam, along with Myron L. Stein and Mark B. Wells, compiled a program for the MANIAC computer that made it possible to plot consecutive integers from 1 to 65,000 on a spiral. The resulting pattern (sometimes called “Ulam’s tablecloth”) is shown in Fig. 204. [ And this is an expanded version of the above Figure 2, so I present it. ? E.G.A.] Please note that even at the edge of the picture, the prime numbers continue to obediently fit onto the straight lines.
The first thing that catches your eye is the clusters of prime numbers on the diagonals, but another tendency for prime numbers to line up along vertical and horizontal lines, on which all the cells free of prime numbers are occupied by odd numbers, is also quite noticeable. Prime numbers falling on straight lines extended beyond a segment that contains consecutive numbers lying on some turn of the spiral can be considered the values of certain quadratic expressions starting with the term 4 x². For example, the sequence of prime numbers 5, 19, 41, 71, located on one of the diagonals in Fig. 204, these are the values taken by the quadratic trinomial 4 x² + 10 x+ 5 at x, equal to 0, 1, 2 and 3. From Fig. 204 it is clear that quadratic expressions that take prime values can be “poor” (giving few prime numbers) and “rich” and that on the “rich” lines there are whole “scatterings” of prime numbers.
By starting the spiral not from 1, but from some other number, we obtain other quadratic expressions for prime numbers aligned along straight lines. Consider a spiral starting with the number 17 (Fig. 205, left). The numbers along the main diagonal running from "northeast" to "southwest" are generated by the quadratic trinomial 4 x² + 2 x+ 17. Substituting positive values x, we get the lower half of the diagonal by substituting negative values for the upper half. If we consider the entire diagonal and rearrange the prime numbers in ascending order, it turns out (and this is a pleasant surprise) that all the numbers are described by a simpler formula x² + x+ 17. This is one of many “generating” formulas for prime numbers discovered back in the 18th century by the great mathematician Leonhard Euler. At x, taking values from 0 to 15, it gives only prime numbers. Therefore, if we continue the diagonal until it fills a 16 x 1 6 square, we see that the entire diagonal is filled with prime numbers.
Euler's most famous quadratic trinomial, producing prime numbers, x² + x+ 41, it turns out if you start the spiral with the number 41 (Fig. 205, right). This trinomial allows you to get 40 consecutive prime numbers that fill the entire diagonal of a 40x4 0 square! It has long been known that of the 2398 first values taken by this trinomial, exactly half are simple. After going through all the values of the famous trinomial that did not exceed 10,000,000, Ulam, Stein and Wells found that the proportion of prime numbers among them was 0.475... . Mathematicians would very much like to discover a formula that allows them to obtain everyone in general x various prime numbers, but so far no such formula has been found. Maybe it doesn't exist.
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
| Rice. 205. Diagonals filled with prime numbers generated by quadratic trinomials x² + x+ 17 (left) and x² + x+ 41 (right). | ||||||||||||||||||||||||||||||||||||||||||||||||||||
The Ulam Spiral raised many new questions regarding patterns and randomness in the distribution of prime numbers. Are there lines containing infinitely many prime numbers? What is the maximum density of distribution of prime numbers along lines? Do the density distributions of prime numbers in the quadrants of Ulam's tablecloth differ significantly, if we assume that it continues indefinitely? The Ulam Spiral is fun, but should be taken seriously.