= Prime number
{title2=$p$}
{wiki}
= Prime
{synonym}
A <prime number> is a <positive integer> $p>1$ whose only positive <divisors> are $1$ and $p$. The first ten <prime numbers> are $2,3,5,7,11,13,17,19,23,29$. In contrast, $12=3\cdot4$ is a <composite number> because it has a positive <divisor> strictly between one and itself. The <integer> one is neither a <prime number> nor a <composite number>: the lower bound $p>1$ is part of the definition. Equivalently, the <divisor function> satisfies $\tau(p)=2$ for a <prime number>, whereas $\tau(1)=1$ and $\tau(n)\geq3$ for every <composite number> $n$.
<Prime numbers> are the building blocks of <positive integers> under <multiplication>. The <fundamental theorem of arithmetic> says that every <integer> greater than one is a <product> of <prime numbers>, with a unique collection of factors when their order is ignored. For example, $12=2\cdot2\cdot3$ and $18=2\cdot3\cdot3$. Their common factors reveal the <greatest common divisor> $6$, and the combined maximum powers reveal the <least common multiple> $36$. A complicated <divisibility> question becomes a comparison of prime exponents.
There is also a useful finite test. If a <composite number> $n$ equals $ab$ with $1<a\leq b$, then $a^2\leq n$. Therefore some <prime factor> is at most $\sqrt n$, and <trial division> only needs to check <prime numbers> up to that <square root>. For $97$, checking $2,3,5,7$ suffices; none divides $97$, so it is a <prime number>. For $91$, the same test finds $7$, giving $91=7\cdot13$. To find many <prime numbers> together, the <sieve of Eratosthenes> reuses the work by marking multiples.
The <division with remainder> calculations for $97$ make the test explicit:
$$
97=2\cdot48+1=3\cdot32+1=5\cdot19+2=7\cdot13+6.
$$
Since $9^2<97<10^2$, these are all the <prime numbers> at most its <square root>, and every <remainder> is nonzero. Thus the calculation certifies a <prime number>, without testing the <integers> $8,9,10,\ldots,96$ individually. In contrast, $91=7\cdot13+0$ gives a <prime factor> and proves that $91$ is a <composite number>.
The definition has a long history. Book VII of <Euclid's Elements> distinguishes <prime numbers> from <composite numbers> through their possible measures; Book IX, Proposition 20 establishes that no finite list exhausts the <prime numbers>. The modern argument under <Euclid's theorem> needs only <divisibility>, so it proves an infinite conclusion without estimating how frequently <prime numbers> occur. https://mathcs.clarku.edu/~djoyce/elements/bookVII/defVII11.html[Euclid, Elements, Book VII, definitions 11–14, David Joyce's edition]{ref} https://mathcs.clarku.edu/~djoyce/elements/bookIX/propIX20.html[Euclid, Elements, Book IX, Proposition 20]{ref}.
Back to article page
