Difference between revisions of "Prime number"

Revision as of 11:12, 17 July 2007

A prime number (or simply prime) is a positive integer $p>1$ whose only positive divisors are 1 and itself. Note that $1$ is usually defined as being neither prime nor composite because it is its only factor among the natural numbers.

Identifying primes

The Sieve of Eratosthenes is a relatively quick method for generating a list of the prime numbers.

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 $2^n+1$ . 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 $2^{2^n}+1$ . Fermat checked the cases n=0,1,2,3,4 and conjectured that all such numbers were prime. However, $2^{2^5}+1=641\cdot 6700417$ . 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 $2^{2^n} + 1$ ). One simply shows that any two Fermat numbers are relatively prime.

Mersenne Primes

A Mersenne prime is a prime of the form $2^n-1$ . 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.

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 $p=ab$ with $a,b\in R$ , then exactly one of a and b is a unit.

@@ Line 14: / Line 14: @@
 === Fermat Primes ===
-A [[Fermat prime]] is a prime of the form <math>2^{2^n}+1</math>. It can easily be shown that for such a number to be prime, ''n'' must be a power of 2. Therefore Fermat primes can also be written as <math>2^{2^n}+1</math>. Fermat checked the cases ''n=0,1,2,3,4'' and conjectured that all such numbers were prime. However, <math>2^{2^5}+1=641\cdot 6700417</math>. In fact, no other Fermat primes have been found.
+A [[Fermat prime]] is a prime of the form <math>2^n+1</math>. 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 <math>2^{2^n}+1</math>.  [[Fermat]] checked the cases ''n=0,1,2,3,4'' and conjectured that all such numbers were prime. However, <math>2^{2^5}+1=641\cdot 6700417</math>. In fact, no other Fermat primes have been found.
-There is an easy proof of the infinitude of primes based on Fermat numbers. One simply shows that any two Fermat numbers are [[relatively prime]].
+There is an easy proof of the infinitude of primes based on Fermat numbers (numbers of the form <math>2^{2^n} + 1</math>). One simply shows that any two Fermat numbers are [[relatively prime]].
 === Mersenne Primes ===
@@ Line 32: / Line 32: @@
 It is not known whether or not there are infinitely many pairs of twin primes.
-Twin Primes, like primes, become rarer as numbers rise.
 == 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 <math>p=ab</math> with <math>a,b\in R</math>, then exactly one of ''a'' and ''b'' is a [[unit]].

Page

Toolbox

Search