# Difference between revisions of "Prime number"

(→Identifying primes) |
|||

Line 35: | Line 35: | ||

=== Gaussian Primes === | === Gaussian Primes === | ||

− | A Gaussian prime is a prime that extends the idea of the traditional prime to the | + | A Gaussian prime is a prime that extends the idea of the traditional prime to the [[Gaussian integer|Gaussian integers]]. One can define this term for any [[ring]], especially number rings. |

== Advanced Definition == | == Advanced Definition == |

## Revision as of 06:50, 15 August 2010

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.

It is well-known that 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, contradiction.

## Contents

## Identifying primes

*Main article: Sieve of Eratosthenes*

The Sieve of Eratosthenes is a relatively quick method for generating a list of the prime numbers. It is a method in which the multiples of all known primes are labeled as composites.

## 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 were prime. However, . In fact, no other Fermat primes have been found.

There is an easy proof of the infinitude of primes based on Fermat numbers (numbers of the form ). One simply shows 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 Lucas-Lehmer test.

### Twin Primes

Two primes that differ by exactly 2 are known as twin primes. The following are the smallest examples:

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.

### 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 a unique factorization domain, then an element *p* of *R* is a **prime** if whenever we write with , then exactly one of *a* and *b* is a unit.