Current location - Training Enrollment Network - Mathematics courses - What is a prime number
What is a prime number
Prime numbers are also called prime numbers. Refers to a natural number greater than 1, except 1 and the integer itself, which cannot be divisible by other natural numbers. In other words, a natural number with only two positive factors (1 and itself) is a prime number. Numbers greater than 1 but not prime numbers are called composite numbers. 1 and 0 are neither prime numbers nor composite numbers. Prime numbers play an important role in number theory.

The smallest prime number is 2, which is also the only even number. The first group of prime numbers are arranged as follows: 2, 3, 5, 7, 1 1, 13, 17, ......

A positive integer that is not a prime number and greater than 1 is called a composite number.

Prime numbers on the prime number table, please see the prime number table.

According to the defined formula:

Let A=n2+b=(n-x)(n+y), and there is no positive integer except n-x= 1. Therefore, there are:

y =(b+NX)/(n-x)(x & lt; N- 1) has no positive integer, so a is a prime number.

Because x

See the Interactive Encyclopedia of Prime Distribution and Indefinite Equation for details.

[Edit this paragraph] fundamental theorem of arithmetic

Fundamental theorem of arithmetic:

Any positive integer n greater than 1 can be uniquely expressed as the product of finite prime numbers: n=p_ 1p_2...p_s, where p_ 1≤p_2 ≤...≤p_s is a prime number.

This expression is also called the standard decomposition of n.

Fundamental theorem of arithmetic is the most basic theorem in elementary number theory. From this theorem, we can redefine the concepts of the greatest common factor and the least common multiple of two integers.

1 cannot be called a prime number, because it is necessary to ensure the uniqueness required by fundamental theorem of arithmetic. This explanation can be found in Hua's Introduction to Number Theory.

[Edit this paragraph] Prime number distribution problem

The distribution of prime numbers refers to the distribution of prime numbers on positive integer sets or their special subsets, such as the number of prime numbers and so on. The results are as follows:

(1) Euclid proved by reduction to absurdity that the number of prime numbers is infinite; Euler also proved this conclusion by analytical method.

(2) Gauss put forward the famous prime number theorem (it was a conjecture at that time, but it was later proved): Let π(x) be the number of prime numbers not exceeding x, then the limit (x tends to infinity).

lim π(x)/(x/Ln x)= 1

A better approximate formula is the li(x) function proposed by Gauss, that is, lim π(x)/lix= 1.

In ...

(3) Dirichlet proved that any arithmetic progression: a, a+d, a+2d, ... a+nd, ... (where a and d are coprime) contains infinite prime numbers.

(4) Lambert conjecture (proved): there must be a prime number between n and 2n, where n is a positive integer greater than 1.

Distribution and probability of prime numbers within one billion

" 10" |4 |40%

" 100" |25 |25%

" 1000" | 168 | 16.8%

" 10000" | 1229 | 12.29%

" 100000" |9592 |9.592%

" 1000000" |78498 |7.8498%

"2000000" | 148933 |7.44665%

" 10000000" |664579 |6.64579%

" 100000000" |576 1455 |5.76 1455%

"200000000" | 1 1078937 |5.5394685%

"300000000" | 16252325 |5.4 1744 167%

"400000000" |2 1336336 |5.334084%

"500000000" |26355877 |5.27 1 1754%

"600000000" |3 13247 13 |5.2207855 %

"700000000" |3625294 1 |5. 17899 157%

"800000000" |4 1 146 189 |5. 143273625%

"900000000" |46009225 |5. 1 12 136 1%

" 1000000000" |50847544 |5.0847544%

It can be seen that the proportion of prime numbers decreases, but the total number increases.

It can be seen that the number of prime numbers is infinite. This conclusion has been proved by the ancient Greek mathematician Euclid in his book Elements of Geometry by reduction to absurdity.

[Edit this paragraph] The construction of prime numbers

How to construct prime numbers, that is, to find a formula that can only produce prime numbers, is an important topic in classical number theory. Many mathematicians have tried this problem. Here are some classic examples.

(1) fermat number f _ n defined by Fermat = 2 (2n)+1. He guessed that fermat number was a prime number. But Euler proved that 64 1 can be divisible by F5. So far, people can't prove whether there are infinite fermat number prime numbers. Some people speculate that almost all fermat number is a composite number.

(2) Gauss proved that a positive N-polygon can be drawn with a ruler if and only if all odd prime factors of n are Fermat prime numbers. In particular, you can use a ruler to make a regular heptagon.

(3) M _ P defined by Mei Sen = 2 p-1. He guessed that when P is a prime number, m _ p is also a prime number, which is called mersenne prime. But this conclusion has also been denied. An important question is: Is there an infinite number of mersenne prime? This conjecture has not been confirmed so far.

(4) A number n is even perfect if and only if n can be written as n = 2 {p- 1} M_p, where p and Mason number M_p are prime numbers. An important question is: Is there an odd perfect number?

(5) Euler and Fermat constructed some polynomials, which all take prime numbers in a certain range, such as: f (n) = n 2-n+41,n= 1, 2 are all prime numbers, ..., 40. An interesting problem is that there are infinitely many prime numbers that can be written as n 2.

(6) Formulas that only produce prime numbers are easy to construct, but they have no theoretical significance. For example, let B_n=((n- 1)! +1)/n, where {x} represents the fractional part of X and [x] represents the integer part of X. Therefore, the function f(n)=n+(n-2)[{-B_n}] only produces prime numbers. This is the application of the famous Wilson theorem, that is, "n is a prime number if and only if (n- 1)!" +1 is divisible by n ".

(7) The traditional screening method uses a theorem: "N is a prime number, if it is not divisible by any prime number not greater than the root number n". Algebra Dictionary, Shanghai Education Press, 1985, p. 259. See Baidu prime number general formula can be expressed by formula, see the following screening method.

[Edit this paragraph] Various conjectures about prime numbers

We have mentioned several conjectures above, such as mersenne prime's infinite conjecture, Fermat's finite prime conjecture and so on. Here are some other important conjectures.

(1) Riemann conjecture. Riemann found through research that most conjectures of prime number distribution depend on the zero position of Riemann zeta function zeta (s). He guessed that those nontrivial zeros all lie on the complex plane and are in a straight line with the real part of 1/2, which is regarded as one of the seven mathematical problems in the Millennium world and an important topic in analytic number theory.

(2) Twin prime conjecture. If both P and p+2 are prime numbers, they are called twin prime numbers. An important question is: Are there infinite pairs of twin prime numbers? There has been no breakthrough in this problem so far.

(3) Goldbach conjecture (a) All even numbers not less than 6 can be expressed as the sum of two odd prime numbers (generally expressed by the code "1+ 1").

(b) Every odd number not less than 9 can be expressed as the sum of three odd prime numbers.

The second part of the problem, estimated by the circle method in analytic number theory, has been proved. The real difficulty is the first part.

[Edit this paragraph] The historical progress of Goldbach's conjecture

Goldbach conjecture was put forward by German mathematician C. Goldbach (1690- 1764) in a letter to the great mathematician Euler on June 7th, 742, so it is called Goldbach conjecture. On June 30th of the same year, Euler replied that this conjecture may be true, but he could not prove it. Since then, this mathematical problem has attracted the attention of almost all mathematicians. Goldbach conjecture has therefore become an unattainable "pearl" in the crown of mathematics.

In 18 and 19 centuries, all number theory experts did not make substantial progress in proving this conjecture until the 20th century. It is directly proved that Goldbach's conjecture is not valid, and people adopt "circuitous tactics", that is, first consider expressing even numbers as the sum of two numbers, and each number is the product of several prime numbers, which is called "almost prime numbers", that is, there are few pixels. If the proposition "every big even number can be expressed as the sum of a number with no more than one prime factor and a number with no more than b prime factors" is recorded as "a+b", then the Coriolis conjecture is to prove that "1+ 1" holds.

"Even number large enough" Chen Jingrun refers to 10 to the power of 5,000,000, that is, 10 plus 500,000 zeros. Goldbach conjecture has not made substantial progress so far.

1920, Norway Brown proved "9+9".

1924, Latmach of Germany proved "7+7".

1932, Esterman of England proved "6+6".

1937, Lacey in Italy successively proved "5+7", "4+9", "3+ 15" and "2+366".

1938, Bukit Tiber of the Soviet Union proved "5+5".

1940, Bukit Tiber of the Soviet Union proved "4+4".

1948, Rini of Hungary proved "1+c", where c is a large natural number.

1956, Wang Yuan of China proved "3+4".

1957, China and Wang Yuan successively proved "3+3" and "2+3".

1962, Pan Chengdong of China and Barba of the Soviet Union proved "1+5", and Wang Yuan of China proved "1+4".

1965, Buchwitz Taber and vinogradov Jr. of the Soviet Union and Pemberley of Italy proved "1+3".

1966, China Chen Jingrun proved "1+2".

[Edit this paragraph] Several English explanations of prime numbers

1. In mathematics, a prime number (or prime number) is a natural number greater than one, and its only positive divisor is one and itself. In short, a prime number is a natural number with exactly two natural number factors. Natural numbers that are greater than one and not prime numbers are called composite numbers. The numbers 0 and 1 are neither prime nor composite. The nature of prime numbers is called prime. Prime numbers are very important in number theory. [From Wikipedia]

2. An integer that is not divisible by any integer except itself and one and has no remainder. [From American Traditional Dictionary]

3. Any integer except 0 or 1 cannot be divisible by any other integer except 1 and the integer itself. [The collegiate bench from Webster's dictionary? Dictionary]

4. A number that can only be divisible by itself and the number one. For example, three and seven are prime numbers. [Excerpted from Longman Dictionary of Contemporary English]

[Edit this paragraph] Screening method

The screening method is a method to find all the prime numbers that do not exceed the natural number n (n > 1). It is said that it was invented by Eratosthenes in ancient Greece (about 274 ~ 194 BC), also known as Eratosthenes sieve.

The specific method is: first, arrange n natural numbers in order. 1 is not a prime number or a composite number and should be crossed out. The second number, 2, is a prime number. After 2, all numbers divisible by 2 are crossed out. The first number not crossed out after 2 is 3, leave 3, and then cross out all the numbers divisible by 3 after 3. The first number not crossed out after 3 is 5, leave 5, and then cross out all the numbers divisible by 5 after 5. If you keep doing this, you will filter out all the composite numbers that don't exceed N, leaving all the prime numbers that don't exceed N, because the Greeks wrote numbers on a wax board, and every time they crossed out a number, they wrote points on it. After the work of finding prime numbers is completed, many points are like a sieve, so Eratosthenes's method is called "Eratosthenes sieve", or "sieve method" for short. Another explanation is that the numbers at that time were written on papyrus, and every time a number was crossed out, a number was dug up. After the work of finding prime numbers is finished, these holes are like sieves. )

The relationship between screening method and formula;

General formula of prime numbers: In 250 BC, the ancient Greek mathematician Eratoseni proposed a screening method:

(a) "To get all prime numbers not greater than a natural number n, just cross out all multiples of prime numbers not greater than √N in 2-N".

(2) Equivalent transformation of the above contents: "If n is a composite number, it has a factor d that satisfies 1

(3) Equivalent transformation of the content of (2): "If the natural number n is not divisible by any prime number not greater than (root sign) √N, then n is a prime number". See (Dictionary of Algebra [Shanghai Education Press] 1985. Drawer is edited by Zhen. Page 259).

(4) The Chinese character of this sentence can be equivalently converted into a formula expressed by English letters:

n = p 1m 1+a 1 = p2m 2+a2 =......=pkmk+ak .( 1)

Where p 1, p2, ..., pk stands for sequential prime numbers 2, 3, 5,,,,. Answer ≠0. That is, n cannot be 2m+0, 3m+0, 5m+0, ..., pkm+0. If the square of n (k+ 1) [note: the following 1, 2, 3, ..., k, (k+ 1) are all footprints, and the numbers behind the letters or I and k are all footprints because they cannot be printed], then n is a prime number.

(5) (1) can be equivalently converted into a set of congruences:

N≡a 1(modp 1),N≡a2(modp2),.....,N AK(modpk)。 (2)

For example, 29,29 cannot be divisible by any prime number 2,3,5 below the root number 29, and 29 = 2x14+1= 3x9+2 = 5x5+4. 29≡ 1 (modulo 2), 29≡2 (modulo 3) and 29≡4 (modulo 5).29 is less than the square 49 of 7, so 29 is a prime number.

The square in the future is represented by "*", that is, ㎡=m*.

Because (2) p 1, p2, ..., pk are pairwise coprime, according to Sun Tzu's theorem (China's remainder theorem), (2) there is a unique solution ... PK in the range of p 1p2.

For example, when k= 1 and N=2m+ 1, the solution is N=3, 5, 7. All the prime numbers in the (3,3 *) interval are obtained.

When k=2, N=2m+ 1=3m+ 1, and the solution is n = 7, 13,19; N=2m+ 1=3m+2, and the solution is n = 5, 1 1,17,23. All prime numbers in the (5,5 *) interval are obtained.

When k=3,

- | 5m+ 1-|- 5m+2-| 5m+3,| 5m+4。 |

- | - | - | - | - |

n = 2m+ 1 = 3m+ 1 = |-3 1-|-7,37-|- 13,43| - 19 - |

n = 2m+ 1 = 3m+2 = |- 1 1,4 1-|- 17,47-| - 23 - | - 29 - |

-

Get all the prime numbers in the (7,7 *) interval.

If we continue like this, we can find all the prime numbers in any large number.