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.

add req­ui­site for divisornumbertheory

Children:

Parents: