Prime Numbers.

Prime Numbers. Prime Numbers, integers greater than 1 that are not the products of the multiplication of any combination of positive integers other than themselves and 1. Of the first ten positive integers greater than 1 (2 through 11), for example, 2, 3, 5, 7, and 11 are prime, whereas 4 (= 2 × 2), 6 (= 2 × 3), 8 (= 2 × 4), 9 (= 3 × 3), and 10 (= 2 × 5) are not. Numbers that are not prime are known as composite numbers. The importance of prime numbers arises from the Fundamental Theorem of Arithmetic: Every integer greater than 1 is a product of one or more prime numbers (possibly with repetitions), and this factorization is unique. For instance, 30 = 2 × 3 × 5, and 28 = 2 × 2 × 7 (or 22 × 7). This theorem reduces the complexity of many mathematical problems concerning integers by allowing them to be restated as problems concerning prime numbers. Mersenne primes are a specific type of prime number that can be derived using the formula 2n - 1, where n is a prime number. When n = 2, for example, (2 × 2) - 1 = 3, which is also prime. Not every prime value of n results in a prime solution to the equation, but the chances of the solution being prime are much greater than for a randomly selected number. Mersenne primes are named after the 17th-century French mathematician Marin Mersenne who discovered them. The ancient Greek mathematician Euclid proved that there are infinitely many prime numbers. The Prime Number Theorem states that large integers are less likely to be prime than small ones. This means that the average separation of consecutive prime numbers increases as the numbers get larger. Primes occur very irregularly among the integers, however, and there is no simple formula for producing them. Primes sometimes occur in very close proximity. Prime twins, for example, are primes with a difference of only 2, such as 11 and 13 or 29 and 31. Mathematicians believe there are an infinite number of prime twins, but it has not yet been mathematically proven. On the other hand, there are arbitrarily large gaps in which there are no primes. For example, by examining sufficiently large numbers it is possible to find a million consecutive numbers, not one of which is prime, immediately followed by a prime twin. In recent years, computers have been applied extensively to the problems of finding new primes, testing whether a particular integer is prime, and factoring a given integer. All three of these processes require very laborious calculations when the numbers involved are large. Effective secret codes have been based on the computational difficulty of factoring very large prime numbers. See Cryptography. Microsoft ® Encarta ® 2009. © 1993-2008 Microsoft Corporation. All rights reserved.