# Prime number

A nat­u­ral num­ber $$n > 1$$ is prime if it has no di­vi­sors other than it­self and $$1$$. Equiv­a­lently, it has the prop­erty that if $$n \mid ab$$ noteThat is, $$n$$ di­vides the product $$ab$$ then $$n \mid a$$ or $$n \mid b$$. Con­ven­tion­ally, $$1$$ is con­sid­ered to be nei­ther prime nor com­pos­ite (i.e. non-prime).

# Examples

• The num­ber $$2$$ is prime, be­cause its di­vi­sors are $$1$$ and $$2$$; there­fore it has no di­vi­sors other than it­self and $$1$$.

• The num­ber $$3$$ is also prime, as are $$5, 7, 11, 13, \dots$$.

• The num­ber $$4$$ is not prime; nei­ther are $$6, 8, 9, 10, 12, \dots$$.

# Properties

• There are in­finitely many primes. (Proof.)

• Every nat­u­ral num­ber may be writ­ten as a product of primes; more­over, this can only be done in one way (if we count “the same product but with the or­der swapped” as be­ing the same: for ex­am­ple, $$2 \times 3 = 3 \times 2$$ is just one way of writ­ing $$6$$). (Proof.)

# How to find primes

If we want to cre­ate a list of all the primes be­low a given num­ber, or the first $$n$$ primes for some fixed $$n$$, then an effi­cient way to do it is the Sieve of Eratos­thenes. (There are other sieves available, but Eratos­thenes is the sim­plest.)

There are many tests for pri­mal­ity and for com­pos­ite­ness.

# More gen­eral concept

This defi­ni­tion of “prime” is, in a more gen­eral ring-the­o­retic set­ting, known in­stead as the prop­erty of ir­re­ducibil­ity. Con­fus­ingly, there is a slightly differ­ent no­tion in this ring-the­o­retic set­ting, which goes by the name of “prime”; this no­tion has a sep­a­rate page on Ar­bital. In the ring of in­te­gers, the two ideas of “prime” and “ir­re­ducible” ac­tu­ally co­in­cide, but that is be­cause the in­te­gers form a ring with sev­eral very con­ve­nient prop­er­ties: in par­tic­u­lar, be­ing a Eu­clidean do­main, they are a prin­ci­pal ideal do­main (PID), and PIDs have unique fac­tori­sa­tion.