A natural number \(n > 1\) is prime if it has no divisors other than itself and \(1\). Equivalently, it has the property that if \(n \mid ab\) noteThat is, \(n\) divides the product \(ab\) then \(n \mid a\) or \(n \mid b\). Conventionally, \(1\) is considered to be neither prime nor composite (i.e. non-prime).

Examples

• The number \(2\) is prime, because its divisors are \(1\) and \(2\); therefore it has no divisors other than itself and \(1\).

• The number \(3\) is also prime, as are \(5, 7, 11, 13, \dots\).

• The number \(4\) is not prime; neither are \(6, 8, 9, 10, 12, \dots\).

Properties

• There are infinitely many primes. (Proof.)

• Every natural number may be written as a product of primes; moreover, this can only be done in one way (if we count “the same product but with the order swapped” as being the same: for example, \(2 \times 3 = 3 \times 2\) is just one way of writing \(6\)). (Proof.)

How to find primes

If we want to create a list of all the primes below a given number, or the first \(n\) primes for some fixed \(n\), then an efficient way to do it is the Sieve of Eratosthenes. (There are other sieves available, but Eratosthenes is the simplest.)

There are many tests for primality and for compositeness.

More general concept

This definition of “prime” is, in a more general ring-theoretic setting, known instead as the property of irreducibility. Confusingly, there is a slightly different notion in this ring-theoretic setting, which goes by the name of “prime”; this notion has a separate page on Arbital. In the ring of integers, the two ideas of “prime” and “irreducible” actually coincide, but that is because the integers form a ring with several very convenient properties: in particular, being a Euclidean domain, they are a principal ideal domain (PID), and PIDs have unique factorisation.

add requisite for divisornumbertheory