Changes

</blockquote>

</blockquote>

The number of primes smaller than a given number <math>N</math> is roughly <math>\frac{N}{\ln(N)}</math>, where <math>\ln(N)</math> is the natural logarithm (base ''e'') of <math>N</math>.<ref>http://home.att.net/~numericana/answer/primes.htm</ref>  This is a formulation of a more general statement known as the [[prime number theorem]].

The number of primes smaller than a given number <math>N</math> is roughly <math>\frac{N}{\ln(N)}</math>, where <math>\ln(N)</math> is the [[natural logarithm]] (base ''[[e]]'') of <math>N</math>.<ref>http://home.att.net/~numericana/answer/primes.htm</ref>  This is a formulation of a more general statement known as the [[prime number theorem]].

==The Prime Numbers==

==The Prime Numbers==

==Alternative Definition==

==Alternative Definition==

Mathematicians prefer the following definition, which is - for integers - equivalent to the one stated above:

Mathematicians often prefer the following definition, which, for integers, is equivalent to the one stated above: <blockquote>''A prime number is a non-unit (i.e., not 1 or -1 for the integers) which whenever it divides the product of two numbers will divide at least one of the factors.''</blockquote>

<blockquote>''A prime number is a non-unit (i.e., not 1 or -1 for the integers) which whenever it divides the product of two numbers will divide at least one of the factors.''</blockquote>

Or in symbolic notation:

Or in symbolic notation:

<math>p \in \mathbb{Z}  \quad prime :\Leftrightarrow p \not\in \{-1, 1\} \wedge (\forall a,b \in \mathbb{Z}: p \vert ab \Rightarrow p \vert a \vee p \vert b) </math>

<math>p \in \mathbb{Z}  \quad prime :\Leftrightarrow p \not\in \{-1, 1\} \wedge (\forall a,b \in \mathbb{Z}: p \vert ab \Rightarrow p \vert a \vee p \vert b) </math>

The advantage of this formulation is that it can be generalized on other structures which allow for addition and multiplication, i.e., rings.

The advantage of this formulation is that it can be generalized on other structures which allow for addition and multiplication, i.e., [[ring]]s. The earlier definition involves the notion of [[irreducibility]].

 

==Unique Factorization==

==Unique Factorization==

According to the [[fundamental theorem of arithmetic]], proven by [[Carl Friedrich Gauss]], every positive integer has a unique factorization into prime numbers.

According to the [[Fundamental Theorem of Arithmetic]], proven by [[Carl Friedrich Gauss]], every positive integer has a unique factorization into prime numbers.

This means that every integer larger than 1, can be expressed as a product of one or more [[prime|primes]] in only one way. For example, 132 = 2 * 2 * 3 * 11. There is no other product of primes that equals 132.

This means that every integer larger than 1, can be expressed as a product of one or more primes in only one way. For example, 132 = 2 * 2 * 3 * 11. There is no other product of primes that equals 132.

Finding the prime factors for large numbers can take considerable time (millions of years) even with the most advanced computers. This is referred to as the prime factorization problem, and it is believed to be NP-complete.

Finding the prime factors for large numbers can take considerable time (millions of years) even with the most advanced computers. This is referred to as the prime factorization problem, and it is believed to be [[NP-complete]].

==Primality testing==

==Primality testing==