A natural number \(n > 1\) is prime if it has no 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 (i.e. non-prime).
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\).
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\)). ( )
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 . (There are other sieves available, but Eratosthenes is the simplest.)
There are manyfor 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 . 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 , they are a (PID), and .
add requisite for divisornumbertheory