Prime number

One Prime number is one natural number with exactly two different natural Greek were interested in the prime numbers and discovered some their characteristics. Although they always had a large attraction over the centuries for humans, the prime numbers are questions concerning up to today many inexplicably.

About two thousand years long one did not know to draw practical use from the knowledge over the prime numbers. This changed only with the arising of electronic calculating machines, where the prime numbers played a central role for example in cryptography.

Table of contents

The smallest prime numbers

The smallest prime numbers are

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...
Consequence A000040 in OEIS

The number of 4 is the smallest compound number: It has exactly three positive divisors (1, 2, 4). The number of 6 is the next larger compound number; it possesses four positive divisors (1, 2, 3, 6). The list of the compound numbers begins also

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25...
Consequence A002808 in OEIS

Practical application

Eine wichtige Rolle spielen Primzahlen 在der Cryptography: Many coding systems, for example RSA, it is based on it that one can multiply very fast large prime numbers, on the other hand however no efficient Factorizing procedure admits is and to all appearances also does not exist. Like that it is problem-free possible within seconds to find and multiply two 500-stellige prime numbers with one another. With the today's methods the recuperation of the two prime factors from this 1000-stelligen product would need against it millions of years.

Prime factorization

It applies for that Fundamental principle of arithmetic: Everyone positive leaves itself clear up to the order as Product from prime numbers represent (see Prime factorization). One calls the prime numbers arising in this representation those Prime factors the number. One calls the difficulties the prime factorization Factorizing problems. One tries it with suitable Factorizing procedure to minimize.

Due to this sentence, thus that each natural number can be represented by multiplication of prime numbers clearly, it takes the prime numbers a special atomic position in mathematics. Alexander K. Dewdney called this that Elements that to a large extent similarly.

Characteristics of prime numbers

With exception of the number 2 are all prime numbers p oddly, because all larger straight numbers can be also still divided except by itself and 1 (at least) by 2. Thus each prime number has the form <math>2k+1</math> except 2; with a natural number <math>k</math>.

Prime numbers of the form 4k + 1 and/or. 4k + 3

Each prime number <math>p>2</math> the form has <math>4k+1</math> or <math>4k+3</math> with a nonnegative whole number <math>k</math>. After that dirichletschen prime number set there are infinitely many prime numbers each of the two kinds.

Each natural number of the form <math>4m+3</math> with a nonnegative whole number <math>m</math> contains at least one prime factor of the form <math>4k+3.</math>

A prime number <math>p>2</math> leaves itself exactly then in the form <math>a^2+b^2</math> with whole numbers <math>a, b</math> write, if <math>p</math> the form <math>4k+1</math> has. In this case the representation is essentially clear, D.h. up to sequence and sign of <math>a, b</math>. This representation corresponds to the prime factorization

<math>p=(a+b\mathrm i)(a b\mathrm i)</math>

in the ring of the whole Gauss numbers.

Prime numbers of the form 6k ± 1

Each prime number <math>p > 3</math> the form has <math>p=6k\pm1</math> with a natural number <math>k</math>. Differently expressed: It applies

<math> p \equiv 1 \pmod 6</math> or <math> p \equiv -1 \pmod 6</math>

(for the notation see Congruence (number theory)).

That small sentence of Fermat

For each prime number p and each natural number <math>a</math> with <math>0< A < p</math> applies:

<math>a^{p-1} \equiv 1 \mod p</math>
or
<math>a^{p-1}-1 \equiv 0 \mod p</math>

There are itself also numbers, which are not prime numbers, however nevertheless, to a part of the Basen A, as prime numbers with restraint and thus the small sentence of Fermat fulfill. One calls such Nichtprimzahlen fermatsche pseudo prime numbers. Pseudo prime numbers, those pseudoprimely to all Basen A are, which divisors of these pseudo prime numbers are not, one calls Carmichael numbers.

Particularly in this connection the problem of pseudo prime numbers shows up: they become of a compound number instead of a prime number used, is no more safe the coding. Therefore prime number tests must be used with such procedures, which can differentiate with a very high probability prime numbers of compound numbers. This probability is of the small sentence when using Fermat as basis alone not highly enough, it gives however safer prime number tests.

Euler

A simple consequence from the small sentence of Fermat is the following statement: For each odd prime number p and each natural number A with <math>2 \le A < p</math> applies, applies either

<math>a^{\frac{p-1}{2}} \equiv 1 \mod p</math>

or

<math>a^{\frac{p-1}{2}} \equiv -1 \mod p.</math>

Binomial coefficient

From that Sentence of Wilson (p is exactly a prime number if <math>(p 1)! \equiv -1 \pmod p</math> it is) follows that for each prime number p and each natural number n the congruence

<math>{{np-1}\choose{p-1}} \equiv 1 \pmod{p}</math>

is fulfilled.

proved 1819that for each prime number p > applies for 2 this congruence:

<math>{{2p-1}\choose{p-1}} \equiv 1 \pmod{p^2}</math>

The mathematician Joseph Wolstenholme (1829-1891) proved then 1862that for each prime number p > applies for 3 the following congruence:

<math>{{2p-1}\choose{p-1}} \equiv 1 \pmod{p^3}</math>

Giuga

From the small sentence of Fermat it follows that for a prime number p applies:

<math> 1^{p-1} + 2^{p-1} +... + (p-1)^{p-1} \equiv -1 \pmod{p}</math>

Example p = 5:

<math>1^4 + 2^4 + 3^4 + 4^4 = 1 + 16 + 81 + 256 = 354 = 71\cdot 5 - 1\equiv -1 \pmod{5}</math>

Giuseppe Giuga it assumed that also the reverse conclusion direction applies that thus a number with this characteristic is always prime. It is not clarified whether this assumption is correct. It admits is however that a Gegenbeispiel more than 10.000 decimal places to have would have. In connection with Giugas assumption become those Giuga numbers examined.

Perrin consequence

For each prime number p it applies that it the member P(p) that Perrin consequence divides.

Lucas consequence

A similar characteristic, as to Perrin consequence, exists also to the Lucas consequence. If p a prime number is, then applies:

<math>L_p \equiv 1 \mod p</math>

or more simply expressed:

(Lp - 1) let itself through p divide, if p a prime number is.
p: 2 3 5 7 11 13 17 19 23 29 31 37
Lp: 3 4 11 29 199 521 3.571 9.349 64.079 1.149.851 3.010.349 54.018.521

Further

Two natural numbers, whose result in sum a prime number, always are divisor-strangely. In particular each combination of two positive natural numbers, into which a prime number additive can be divided, is divisor strange.

Procedure for the examination of the Primalitaet of a number

If one liked to know whether a number is a prime number, then one has for it different possibilities available, which have one of the characteristics specified above as basis usually. The most well-known and oldest are probably that Filter of the Eratosthenes. In practice that becomes most frequent Miller Rabin test used, which has an extremely fast running time, however with small probability beside it to lie can. For attention that has in the last years AKS Primzahltest ensured, which proves that it is possible, numbers in polynomialer running time to test (Prime is in P) is clearly slower, however in practice than the Miller Rabin test. These procedures and further variants are under Prime number test described more exactly.

Largest well-known prime number

The Greek in the fourth century before Christ it stated that there are many prime numbers infinitely; this statement becomes as Sentence of Euklid designated. Euklid led one Contradiction proof for the correctness of this sentence: If one proceeds from the assumption that only finally many prime numbers exist, then from it the existence of a further prime number, which represents a logical contradiction to the acceptance, follows. Therefore the acceptance is wrong, and there are infinitely many prime numbers. Today one knows a whole set of Proofs for the sentence of Euklid.

The sentence of Euklid means that there is no largest prime number. It is however no procedure well-known, which generates efficiently of any size prime numbers, so that it always one largest well-known Prime number gave, since then humans with prime numbers is concerned. At present it is <math>2^{25.964.951}-1</math>, a number with 7.816.230 (decimal) places, found to 18. February 2005, after 50 days computing time on 2.4 GHz a computer, of Dr. Martin Nowak within the framework of the George Woltmans GIMPS project to the search of Mersenne prime numbers. For the first prime number proof of a number with more than 10 million decimal places those has Electronic Frontier Foundation a price of 100.000 US dollar written out.

The largest well-known prime number was nearly always one Mersenne prime number, thus of the form <math>2^n-1</math>, there in this special case that Lucas Lehmer test to be used, a prime number test very fast in the comparison to the general situation can. With the search for large prime numbers therefore only numbers these are examined or a similarly suitable type on Primalitaet. One knows that between the largest and the second largest well-known prime number (<math>2^{24.036.583}-1</math>) more than <math>10^{7.500.000}</math> further, unknown prime numbers lie. The exact identification of such prime numbers enjoys however of a comparatively small interest, since it is much more aufwaendiger than for example a finding of a still larger Mersenne prime number.

Distribution of the prime numbers

One thought naturally also over it, like many prime numbers it within a limited range from 1 to for example 1.000.000 gives. With the time some naeherungsformeln were developed and improved.

The function for the distribution is <math>\pi(x)</math>, whereby the number of prime numbers up to the border x one returns the delivery. Example:

<math>\pi(10) = 4 \; \ \pi(100) = 25 \; \ \pi(1000) = 168 </math>

Different mathematicians made themselves now to find functions <math>\pi(x)</math> approximate.

That Prime number set meant that

<math>\pi(x) \sim \frac{x}{\ln x}</math>

, D applies.h. that the quotient from left and right side for <math>x\to\infty</math> against 1 strives.

That dirichletsche prime number set on the other hand the view up Remainder classes on: It is <math>m</math> a natural number. Is <math>a</math> a whole number, too <math>m</math> not divisor-strangely is, then those can arithmetic consequence

<math>a, a+m, a+2m, a+3m, \ldots</math>

contain at the most one prime number, because all consequence members by the largest common divisor of <math>a</math> and <math>m</math> are divisible. Is <math>a</math> but <math>m</math> divisor-strangely too;, thus the dirichletsche prime number set means that the consequence contains many prime numbers infinitely. For example there are many prime numbers of the form infinitely <math>4k+1</math> and infinitely many the form <math>4k+3</math> (<math>k</math> goes through in each case the nonnegative natural numbers).

This statement can be specified still in the following form: It applies

<math>\lim_{x\to\infty}\frac{\#\{p \ \mathrm{prim}, \ p\leq x \ \mathrm{und} \ p\equiv a\pmod m\}}{\#\{p \ \mathrm{prim}, \ p\leq x\}}=\frac1{\phi(m)};</math>

is <math>\phi(m)</math> those Euler?-function. In this sense lie thus for a firm <math>m</math> in the remainder classes <math>a+m\mathbb Z</math> with <math>\mathrm{ggT}(a, m)=1</math> "directly in each case many" prime numbers.

See also: Ulam spiral

Formulas for the generation of prime numbers

One does not know a formula p(n), those when inserting of n the nth prime number returns the delivery. There are however formulas, with which a certain probability exists that the produced numbers could be a prime number. Nothing the defiance must be tested the produced numbers on their characteristic as prime number.

Already Euler gave the formulas to <math>ñ2+n+17</math> and <math>ñ2-n+41</math> on, for 0 < n < 16 and/or. 0 < n < 41 prime numbers supply. Even for larger values of <math>n</math> supply the two formulas many prime numbers, because the result never < by prime numbers p; 17 and/or. p < 41 is integral divisible. Generally there are many such formulas <math>añ2+bn+c</math>, whereby itself the remarkable Ulam spiral explained.

The most popular is those the Mersenne number <math>M_n = 2^n-1</math> with <math>M_n</math> a prime number is.

Also admits is an application of the sentence of Euklid, with on that Primorial a 1 is added:

<math>p \ # + 1 = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1</math>

Here all successive prime numbers are <math>p_n=p</math> from 2 to; multiplies with one another.

Special prime numbers and prime number constellations

Why isn't the number of 1 a prime number?

The simplest answer to the question, why the 1 is not a prime number, quotes the definition:

  • A natural number becomes then prime number called, if it has exactly two natural divisors.
    The number of 1 has only a natural divisor (the 1). Therefore it is not by definition a prime number.

The following answers deal with the purpose of this definition:

  • Thus one a clear Prime factorization bekommt (man hätte sonst beliebig viele 1-Faktoren mit drin).
  • Weil 1 eine Einheit ist (siehe den Artikel Primelement).
  • Weil man ansonsten bei nahezu allen Aussagen über Primzahlen schreiben müsste: „Für alle Primzahlen mit Ausnahme der 1 gilt...“. Beispielsweise in der Theorie der endlichen Körper.

A mathematical system is finally arbitrarily selected from an infinite number of possible systems. Its relevance receives it thereby whether it nontrivial Characteristics has. One produces two different systems, whereby in the first 1 a prime number is, and in second not, and states with the fact that the first system is very boring, and which is so interesting second (in that the 1 a prime number is not) that it forms today one of the most important basic modules of the global economy (see ). One could define now naturally also a system, in which the 2 no prime number is (or 3 or the 5...), but as long as one understood the conventional system not yet completely, these systems are interesting only for mathematicians.

See also for this:

Prime number gaps

The difference p2 - p1 between neighbouring prime numbers p1 < p2 becomes Prime number gap called. Pairs of prime numbers with the minimum distance 2 are called Prime number twins, for example 5 and 7 or 11 and 13.

Generally the number of compound numbers varies between two arbitrary successive prime numbers. See Prime number gap

Verallgemeinerung

In that the concept becomes that Prime number on the elements of any commutative unitary Ring generalized. The appropriate terms are Prime element and irreducible element.

The prime numbers and their negatives are then exactly the prime elements and also exactly the irreducible elements of the ring that . In factorial rings, those are rings with clear prime factorizing, fall the terms Prime element and irreducible element together; generally the quantity of the prime elements is however only one Subset the quantity of the irreducible elements.

In particular in the pay-theoretically important case that Dedekindringe take over Prime ideals the role of the prime numbers.

Tables of prime numbers

Literature

  • Paolo Ribenboim: The new Book OF prime NUMBER record. 3. Aufl., Springer publishing house, New York, 1996, ISBN 0-387-94457-5
  • Marcus you Sautoy: The music of the prime numbers. On the traces of the largest mystery of mathematics. Publishing house C.H.Beck, Munich, 2004, ISBN 3-406-52320-X
  • W?adys?aw Narkiewicz: The development OF prime NUMBER Theory. Springer publishing house, Berlin 2000. ISBN 3-540-66289-8

Web on the left of


- word origin, synonyms and translations


- learning and teaching materials

 

  > German to English > de.wikipedia.org (Machine translated into English)