Difference between revisions of "Prime number"
Armalite46 (talk | contribs) (Added information about twin primes; seive of eratosthenes) |
(→Mersenne Primes) |
||
Line 21: | Line 21: | ||
=== Mersenne Primes === | === Mersenne Primes === | ||
− | A [[Mersenne prime]] is a prime of the form <math>2^n-1</math>. For such a number to be prime, ''n'' must itself be prime. Compared to other numbers of comparable sizes, Mersenne numbers are easy to check for primality because of the [ | + | A [[Mersenne prime]] is a prime of the form <math>2^n-1</math>. For such a number to be prime, ''n'' must itself be prime. Compared to other numbers of comparable sizes, Mersenne numbers are easy to check for primality because of the [(https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test) (Lucas-Lehmer test)], severely reducing the amount of computation needed. |
=== Twin Primes === | === Twin Primes === |
Revision as of 16:10, 12 September 2017
A prime number (or simply prime) is a positive integer whose only positive divisors are 1 and itself.
Note that
is usually defined as being neither prime nor composite because it is its only factor among the natural numbers.
There are an infinite number of prime numbers. A standard proof attributed to Euclid notes that if there are a finite set of prime numbers , then the number
is not divisible by any of them, but
must have a prime factor, which leads to a direct contradiction.
Contents
Identifying primes
- Main article: Sieve of Eratosthenes
The Sieve of Eratosthenes is a relatively simplistic algorithm for generating a list of the first few prime numbers. It is a method in which the multiples of all known primes are labeled as composites, and subsequently crossed out, starting with multiples of two, then three, then five, and so on. For example, circle 2, and cross out all other multiples of two. Then circle 3, and cross out all multiples of three. Repeat with all other prime numbers as needed. Although simple to understand, it is inefficient for finding large primes.
Importance of Primes
According to the Fundamental Theorem of Arithmetic, there is exactly one unique way to factor a positive integer into a product of primes (permutations not withstanding). This unique prime factorization plays an important role in solving many kinds of number theory problems.
Famous Primes
Fermat Primes
A Fermat prime is a prime of the form . It can easily be shown that for such a number to be prime, n must not have any odd divisor larger than 1 and so must be a power of 2. Therefore all Fermat primes have the form
. Fermat checked the cases
and conjectured that all such numbers of the form were prime. However,
.
also fails if
;
. In fact, no other Fermat primes have been found to date.
There is an easy proof of the infinitude of primes based on Fermat numbers (numbers of the form ). Just show that any two Fermat numbers are relatively prime.
Mersenne Primes
A Mersenne prime is a prime of the form . For such a number to be prime, n must itself be prime. Compared to other numbers of comparable sizes, Mersenne numbers are easy to check for primality because of the [(https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test) (Lucas-Lehmer test)], severely reducing the amount of computation needed.
Twin Primes
Two primes that differ by exactly 2 are known as twin primes. The following are the first few pairs of twin primes:
3, 5
5, 7
11, 13
17, 19
29, 31
41, 43
It is not known whether or not there are infinitely many pairs of twin primes. This is known as the Twin Prime Conjecture, which is a specific instance of the Hardy-Littlewood conjecture.
Gaussian Primes
A Gaussian prime is a prime that extends the idea of the traditional prime to the Gaussian integers. One can define this term for any ring, especially number rings.
Advanced Definition
When the need arises to include negative divisors, a prime is defined as an integer p whose only divisors are 1, -1, p, and -p. More generally, if R is an integral domain, then a nonzero element p of R is a prime if whenever we write with
, then exactly one of a and b is a unit.