prime number (or a prime) is a natural number that has exactly two distinct natural number divisors: 1 and itself. The smallest twenty-five prime numbers (all the prime numbers under 100) 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
An infinitude of prime numbers exists, as demonstrated by Euclid around 300 BC,[1] although the density of prime numbers within natural numbers is 0. The number 1 is by definition not prime. The fundamental theorem of arithmetic establishes the central role of primes in number theory: any positive integer n can be factored into primes, written as a product of primes or powers of different primes (including the empty product of factors for 1). Moreover, this factorization is unique except for a possible reordering of the factors.
The property of being prime is called primality. Verifying the primality of a given number n can be done by trial division. The simplest trial division method tests whether n is a multiple of an integer m between 2 and √n. If n is a multiple of any of these integers then it is a composite number, and so not prime; if it is not a multiple of any of these integers then it is prime. As this method requires up to √n trial divisions, it is only suitable for relatively small values of n. More sophisticated algorithms, which are much more efficient than trial division, have been devised to test the primality of large numbers.
There is no known useful formula that yields all of the prime numbers and no composites. However, the distribution of primes, that is to say, the statistical behaviour of primes in the large can be modeled. The first result in that direction is the prime number theorem which says that the probability that a given, randomly chosen number n is prime is inversely proportional to its number of digits, or the logarithm of n. This statement has been proven since the end of the 19th century. The unproven Riemann hypothesis dating from 1859 implies a refined statement concerning the distribution of primes.
Despite being intensely studied, there remain some open questions around prime numbers which can be stated simply. For example, Goldbach's conjecture, which asserts that any even natural number greater than two can be expressed as the sum of two primes, and the twin prime conjecture, which says that there are infinitely many twin primes (pairs of primes whose difference is two), have been unresolved for more than a century, notwithstanding the simplicity of their statements.
Prime numbers give rise to various generalizations in other mathematical domains, mainly algebra, notably the notion of prime ideals.
Primes are applied in several routines in information technology, such as public-key cryptography, which makes use of the difficulty of factoring large numbers into their prime factors. Searching for big primes, often using distributed computing, has stimulated studying special types of primes, chiefly Mersenne primes whose primality is comparably quick to decide. As of 2011[update], the largest known prime number has about 13 million decimal digits.[2]
The fundamental theorem of arithmeticMain article: Fundamental theorem of arithmetic
The crucial importance of prime numbers to number theory and mathematics in general stems from the fundamental theorem of arithmetic which states that every positive integer larger than 1 can be written as a product of one or more primes in a way which is unique except possibly for the order of the prime factors. Primes can thus be considered the “basic building blocks” of the natural numbers. For example, we can write:
23244 = 2 · 2 · 3 · 13 · 149
= 22 · 3 · 13 · 149. (22 denotes the square or second power of 2.)
As in this example, the same prime factor may occur multiple times. A decomposition:
n = p1 · p2 · ... · pt
of a number n into (finitely many) prime factors p1, p2, ... to pt is called prime factorization of n. The fundamental theorem of arithmetic can be rephrased so as to say that any factorization into primes will be identical except for the order of the factors. So, albeit there are many prime factorization algorithms to do this in practice for larger numbers, they all have to yield the same result.
If p is a prime number and p divides a product ab of integers, then p divides a or p divides b. This proposition is known as Euclid's lemma. It is used in some proofs of the uniqueness of prime factorizations.
The number of prime numbersMain article: Euclid's theorem
There are infinitely many prime numbers. Another way of saying this is that the sequence
2, 3, 5, 7, 11, 13, ...
of prime numbers never ends. This statement is referred to as Euclid's theorem in honor of the ancient Greek mathematician Euclid, since the first known proof for this statement is attributed to him. Many more proofs of the infinitude of primes are known, including an analytical proof by Euler, Goldbach's proof based on Fermat numbers,[10] Fürstenberg's proof using general topology and Kummer's elegant proof.
The largest known primeMain articles: Largest known prime and Mersenne prime
Since the dawn of electronic computers the largest known prime has almost always been a Mersenne prime because there is a fast algorithm, the Lucas–Lehmer primality test, for these numbers. Some of these primes have been found using distributed computing, such as the Great Internet Mersenne Prime Search. On October 22, 2009, this project was awarded a US$100,000 prize for first discovering a prime with at least 10 million digits.[16] The Electronic Frontier Foundation also offers $150,000 and $250,000 for primes with at least 100 million digits and 1 billion digits, respectively.[17] Other projects searching primes are PrimeGrid and Wieferich@Home, which tries to find the third Wieferich prime.
Some of the largest primes not known to have any particular form (that is, no simple formula such as that of Mersenne primes) have been found by taking a piece of semi-random binary data, converting it to a number n, multiplying it by 256k for some positive integer k, and searching for possible primes within the interval [256kn + 1, 256k(n + 1) − 1].
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
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
An infinitude of prime numbers exists, as demonstrated by Euclid around 300 BC,[1] although the density of prime numbers within natural numbers is 0. The number 1 is by definition not prime. The fundamental theorem of arithmetic establishes the central role of primes in number theory: any positive integer n can be factored into primes, written as a product of primes or powers of different primes (including the empty product of factors for 1). Moreover, this factorization is unique except for a possible reordering of the factors.
The property of being prime is called primality. Verifying the primality of a given number n can be done by trial division. The simplest trial division method tests whether n is a multiple of an integer m between 2 and √n. If n is a multiple of any of these integers then it is a composite number, and so not prime; if it is not a multiple of any of these integers then it is prime. As this method requires up to √n trial divisions, it is only suitable for relatively small values of n. More sophisticated algorithms, which are much more efficient than trial division, have been devised to test the primality of large numbers.
There is no known useful formula that yields all of the prime numbers and no composites. However, the distribution of primes, that is to say, the statistical behaviour of primes in the large can be modeled. The first result in that direction is the prime number theorem which says that the probability that a given, randomly chosen number n is prime is inversely proportional to its number of digits, or the logarithm of n. This statement has been proven since the end of the 19th century. The unproven Riemann hypothesis dating from 1859 implies a refined statement concerning the distribution of primes.
Despite being intensely studied, there remain some open questions around prime numbers which can be stated simply. For example, Goldbach's conjecture, which asserts that any even natural number greater than two can be expressed as the sum of two primes, and the twin prime conjecture, which says that there are infinitely many twin primes (pairs of primes whose difference is two), have been unresolved for more than a century, notwithstanding the simplicity of their statements.
Prime numbers give rise to various generalizations in other mathematical domains, mainly algebra, notably the notion of prime ideals.
Primes are applied in several routines in information technology, such as public-key cryptography, which makes use of the difficulty of factoring large numbers into their prime factors. Searching for big primes, often using distributed computing, has stimulated studying special types of primes, chiefly Mersenne primes whose primality is comparably quick to decide. As of 2011[update], the largest known prime number has about 13 million decimal digits.[2]
The fundamental theorem of arithmeticMain article: Fundamental theorem of arithmetic
The crucial importance of prime numbers to number theory and mathematics in general stems from the fundamental theorem of arithmetic which states that every positive integer larger than 1 can be written as a product of one or more primes in a way which is unique except possibly for the order of the prime factors. Primes can thus be considered the “basic building blocks” of the natural numbers. For example, we can write:
23244 = 2 · 2 · 3 · 13 · 149
= 22 · 3 · 13 · 149. (22 denotes the square or second power of 2.)
As in this example, the same prime factor may occur multiple times. A decomposition:
n = p1 · p2 · ... · pt
of a number n into (finitely many) prime factors p1, p2, ... to pt is called prime factorization of n. The fundamental theorem of arithmetic can be rephrased so as to say that any factorization into primes will be identical except for the order of the factors. So, albeit there are many prime factorization algorithms to do this in practice for larger numbers, they all have to yield the same result.
If p is a prime number and p divides a product ab of integers, then p divides a or p divides b. This proposition is known as Euclid's lemma. It is used in some proofs of the uniqueness of prime factorizations.
The number of prime numbersMain article: Euclid's theorem
There are infinitely many prime numbers. Another way of saying this is that the sequence
2, 3, 5, 7, 11, 13, ...
of prime numbers never ends. This statement is referred to as Euclid's theorem in honor of the ancient Greek mathematician Euclid, since the first known proof for this statement is attributed to him. Many more proofs of the infinitude of primes are known, including an analytical proof by Euler, Goldbach's proof based on Fermat numbers,[10] Fürstenberg's proof using general topology and Kummer's elegant proof.
The largest known primeMain articles: Largest known prime and Mersenne prime
Since the dawn of electronic computers the largest known prime has almost always been a Mersenne prime because there is a fast algorithm, the Lucas–Lehmer primality test, for these numbers. Some of these primes have been found using distributed computing, such as the Great Internet Mersenne Prime Search. On October 22, 2009, this project was awarded a US$100,000 prize for first discovering a prime with at least 10 million digits.[16] The Electronic Frontier Foundation also offers $150,000 and $250,000 for primes with at least 100 million digits and 1 billion digits, respectively.[17] Other projects searching primes are PrimeGrid and Wieferich@Home, which tries to find the third Wieferich prime.
Some of the largest primes not known to have any particular form (that is, no simple formula such as that of Mersenne primes) have been found by taking a piece of semi-random binary data, converting it to a number n, multiplying it by 256k for some positive integer k, and searching for possible primes within the interval [256kn + 1, 256k(n + 1) − 1].
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]