Prime number

by Patrick Stevens Jun 20 2016 updated Jul 27 2016

The prime numbers are the "building blocks" of the counting numbers.

A Natural number $~$n > 1$~$ is prime if it has no [divisor_number_theory divisors] other than itself and $~$1$~$. Equivalently, it has the property that if $~$n \mid ab$~$ %%note:That is, $~$n$~$ divides the product $~$ab$~$%% then $~$n \mid a$~$ or $~$n \mid b$~$. Conventionally, $~$1$~$ is considered to be neither prime nor [composite_number composite] (i.e. non-prime).



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 Sieve of Eratosthenes]. (There are other sieves available, but Eratosthenes is the simplest.)

There are many [primality_testing 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 Euclidean domain], they are a Principal ideal domain (PID), and [pid_implies_ufd PIDs have unique factorisation].

[todo: add requisite for divisornumbertheory]