Prime numbers are the indivisible building blocks of the positive integers. Multiplication can hide structure: the number $60$ may be written as $2^2\cdot 3\cdot 5$, while $97$ resists every nontrivial factorisation. The notion of a prime number isolates exactly the integers that cannot be decomposed further under multiplication, and it makes divisibility, greatest common divisor, modular arithmetic, and unique factorisation possible as systematic theories. In elementary arithmetic, primes play the role that atoms play in a multiplicative monoid: every positive integer is assembled from them, and the assembly is unique up to ordering. In algebra, the same idea reappears as [prime ideals](/page/Ideal), irreducible elements, valuation theory, and the arithmetic of rings. In analytic number theory, the central question becomes not what primes are, but how they are distributed among the natural numbers. ## Definition The central question is whether a [natural number](/page/Natural%20Number) has any genuine multiplicative decomposition. A prime number is one that has survived every attempt to factor it into smaller positive integers: its only positive divisors are forced by the identity element and by the number itself. [definition: Prime Number] A natural number $p \in \mathbb{N}$ is a prime number if $p \ge 2$ and the only positive divisors of $p$ are $1$ and $p$. [/definition] To make that definition usable in calculations, we also need the underlying language of divisibility. Divisibility records whether a multiplication problem can be solved inside the integers, and it is the relation against which primality is measured. [definition: Divides] Let $a,b \in \mathbb{Z}$. We say that $a$ divides $b$, and write $a \mid b$, if there exists $k \in \mathbb{Z}$ such that \begin{align*} b = ka. \end{align*} [/definition] When divisors are taken in $\mathbb{Z}$ rather than in $\mathbb{N}$, this definition says that the integer divisors of a prime $p$ are exactly $-p$, $-1$, $1$, and $p$. To understand the opposite side of the classification, we next name the numbers that do admit a genuine decomposition into smaller positive factors. [definition: Composite Number] A natural number $n \in \mathbb{N}$ is composite if there exist natural numbers $a,b \in \mathbb{N}$ such that \begin{align*} n = ab, \qquad 1 < a < n, \qquad 1 < b < n. \end{align*} [/definition] The number $1$ sits outside both classes: it is the multiplicative identity, not a building block. The divisor definition also has a practical limitation: it describes $p$ by listing its own factors, but many arguments need to recognize when $p$ must divide one factor of a product $ab$. The obstruction is that a divisor of a product need not divide either factor individually; the following definition singles out numbers for which this obstruction never occurs. [definition: Euclidean Prime] Let $p \in \mathbb{N}$ with $p \ge 2$. We say that $p$ is a Euclidean prime if for all $a,b \in \mathbb{Z}$, \begin{align*} p \mid ab \implies p \mid a \text{ or } p \mid b. \end{align*} [/definition] The product-divisibility definition is deliberately separated from the divisor definition because, in more general algebraic settings, the two ideas can diverge. Over the integers they coincide, and the characterisations below explain why primality can be recognised through greatest common divisors, products, and quotient rings. ## Equivalent Characterisations The first characterisation makes precise the promised comparison between ordinary primes and Euclidean primes. It says that, in $\mathbb{Z}$, having no nontrivial positive divisors is exactly the same as detecting prime factors inside products. [quotetheorem:9877] This equivalence is often used through greatest common divisors. If a prime $p$ does not divide an integer $a$, then $a$ has no nontrivial common factor with $p$. This gives a test that is often easier to use in congruence calculations. [quotetheorem:9878] This characterisation explains why primes behave so cleanly in modular arithmetic. The same gcd dichotomy is what lets a prime factor be detected inside a product, which leads to the next standard form of primality. [quotetheorem:729] Euclid's lemma is the first place where primality shows its full strength. It also explains the basic modular-arithmetic contrast without requiring any ring language. A residue modulo $n$ is a class of integers with the same remainder after division by $n$, and multiplying residues means multiplying representatives and then reducing modulo $n$. For a prime modulus $p$, Euclid's lemma says that if $ab$ is congruent to $0$ modulo $p$, then $a$ or $b$ is already congruent to $0$ modulo $p$. Thus two nonzero residues modulo a prime cannot multiply to the zero residue. For a composite modulus $n=ab$ with $1<a<n$ and $1<b<n$, the nonzero residues represented by $a$ and $b$ do multiply to $0$ modulo $n$. This elementary product test is the modular shadow of primality, and the examples below make the contrast concrete. ## Examples Small examples are useful because the definition is exact rather than asymptotic. The first primes are found by checking divisors up to the square root, not by checking every possible divisor. [example: Small Prime Numbers] The numbers $2,3,5,7,11,13$ are prime. To check this by the definition, it is enough to rule out positive divisors $d$ with $2 \le d \le \sqrt p$: if $p=ab$ with $1<a<p$ and $1<b<p$, then $a>\sqrt p$ and $b>\sqrt p$ would imply $ab>\sqrt p\sqrt p=p$, contradicting $ab=p$. For $2$ and $3$, there is no natural number $d$ satisfying $2 \le d \le \sqrt2$ or $2 \le d \le \sqrt3$. For $5$ and $7$, the only possible value is $d=2$, and \begin{align*} 5 = 2\cdot 2+1, \qquad 7 = 2\cdot 3+1. \end{align*} For $11$ and $13$, the only possible values are $d=2$ and $d=3$, and \begin{align*} 11 = 2\cdot 5+1, \qquad 11 = 3\cdot 3+2, \qquad 13 = 2\cdot 6+1, \qquad 13 = 3\cdot 4+1. \end{align*} Thus none of these possible nontrivial divisors actually divides the corresponding number, so each of $2,3,5,7,11,13$ has only positive divisors $1$ and itself. [/example] This example also shows why $2$ is special: it is the only even prime. Every even natural number greater than $2$ is divisible by $2$ and has a proper positive divisor, and this makes the exclusion of composite numbers visible at the smallest scale. A boundary example prevents a common mistake. The number $1$ behaves multiplicatively like an identity, so including it among primes would make prime decompositions nonunique in a meaningless way. [example: Why One Is Not Prime] The number $1$ is not prime because the definition of prime number requires $p \ge 2$. The exclusion also preserves uniqueness of prime factorisations: since $1\cdot n=n$ for every integer $n$, inserting factors of $1$ never changes a product. For example, \begin{align*} 1\cdot 2\cdot 3 = 2\cdot 3 = 6. \end{align*} Inserting two factors of $1$ gives \begin{align*} 1\cdot 1\cdot 2\cdot 3 = 1\cdot (1\cdot 2\cdot 3) = 1\cdot 6 = 6. \end{align*} More generally, for every $m\in\mathbb{N}$, \begin{align*} \underbrace{1\cdot 1\cdots 1}_{m\text{ factors}}\cdot 2\cdot 3 = 1\cdot 2\cdot 3 = 6. \end{align*} Thus treating $1$ as prime would give infinitely many decompositions of the same number that differ only by extra identity factors, so $1$ is kept outside the class of prime numbers. [/example] Composite numbers demonstrate the opposite side of the definition. They are not merely large numbers; they are numbers with a genuine factorisation into smaller natural numbers. [example: Composite Numbers and Failed Product Divisibility] The number $12$ is composite because it has a factorisation into smaller natural numbers: \begin{align*} 12 = 3\cdot 4. \end{align*} The inequalities required in the definition are \begin{align*} 1<3<12 \end{align*} and \begin{align*} 1<4<12. \end{align*} Thus $3$ and $4$ are genuine positive factors of $12$, so $12$ is not prime. The same factorisation shows that $12$ fails the product-divisibility property enjoyed by primes. Since \begin{align*} 3\cdot 4 = 12 = 1\cdot 12, \end{align*} there exists an integer $k=1$ such that $3\cdot 4=k\cdot 12$, so $12\mid 3\cdot 4$. But $12\nmid 3$: if $12\mid 3$, then $3=12k$ for some $k\in\mathbb{Z}$, which is impossible because $12k\le 0$ when $k\le 0$ and $12k\ge 12$ when $k\ge 1$. Similarly, $12\nmid 4$: if $4=12k$ for some $k\in\mathbb{Z}$, then $12k\le 0$ when $k\le 0$ and $12k\ge 12$ when $k\ge 1$, never giving $4$. Therefore $12\mid 3\cdot 4$ while $12\nmid 3$ and $12\nmid 4$. In modular arithmetic this appears as a zero-divisor calculation: \begin{align*} 3\cdot 4=12\equiv 0\pmod{12}. \end{align*} The residue classes of $3$ and $4$ are both nonzero modulo $12$, but their product is zero, so composite moduli can contain zero divisors. [/example] Prime and composite numbers also behave differently inside congruence arithmetic. The contrast between modulus $5$ and modulus $6$ is the smallest useful illustration. [example: Prime Versus Composite Modulus] Modulo $5$, the nonzero residue classes are $1,2,3,4$. Each one has a multiplicative inverse because we can exhibit a product congruent to $1$ modulo $5$: \begin{align*} 1\cdot 1=1\equiv 1\pmod{5}. \end{align*} Also, \begin{align*} 2\cdot 3=6=1+5\equiv 1\pmod{5}. \end{align*} The same equality gives \begin{align*} 3\cdot 2=6=1+5\equiv 1\pmod{5}. \end{align*} Finally, \begin{align*} 4\cdot 4=16=1+3\cdot 5\equiv 1\pmod{5}. \end{align*} Thus \begin{align*} 1^{-1}\equiv 1,\quad 2^{-1}\equiv 3,\quad 3^{-1}\equiv 2,\quad 4^{-1}\equiv 4\pmod{5}. \end{align*} Modulo $6$, the nonzero residue classes $2$ and $3$ behave differently. Their product is \begin{align*} 2\cdot 3=6=1\cdot 6\equiv 0\pmod{6}. \end{align*} However, \begin{align*} 2\not\equiv 0\pmod{6} \end{align*} because $6\nmid 2$, and \begin{align*} 3\not\equiv 0\pmod{6} \end{align*} because $6\nmid 3$. Therefore modulo $6$ two nonzero residue classes can multiply to zero, while modulo $5$ every nonzero residue class listed above has an inverse. [/example] The examples show the local behaviour of individual primes and composites. The main properties explain why these local tests control the structure of every positive integer. ## Properties The basic structural theorem says that primes are not rare exceptions to multiplication; they generate all positive integers. This is the theorem that justifies calling primes the building blocks of arithmetic. [quotetheorem:723] Existence of prime decompositions still leaves a serious ambiguity: an integer might conceivably be assembled from two different collections of prime factors. Without a uniqueness principle, prime factorisation would not support reliable definitions depending on exponents, such as valuations or arithmetic functions. The needed strengthening is a canonical form theorem: once the prime factors are written with their exponents, no hidden alternative decomposition remains except for reordering the primes. This is what makes later uses of prime factorisation depend on the integer itself rather than on a chosen factorisation. [quotetheorem:730] The exponent form of the factorisation turns multiplicative questions into bookkeeping about prime powers. Since every integer is governed by primes, the next global question is whether these building blocks form a finite stock or an endless supply. [quotetheorem:724] This theorem turns primality from a finite classification into a distribution problem. Once there are infinitely many primes, it becomes meaningful to ask how often they occur; before that global question, there is also a practical finite test for deciding whether a given integer is prime. For practical recognition, the [square-root test](/theorems/9879) gives a finite primality criterion. It works because a nontrivial factorisation $n=ab$ must place at least one factor at or below $\sqrt n$. [quotetheorem:9879] The [square-root test](/theorems/9879) is conceptually simple but not efficient for very large integers. Modern primality testing studies faster algorithms, especially because large primes are central in computational number theory and cryptography. ## Relationship to Other Concepts Prime numbers are the entry point to several larger theories. In modular arithmetic, a prime modulus $p$ produces the finite field $\mathbb{Z}/p\mathbb{Z}$, where division by nonzero residue classes is valid. In [group theory](/page/Group), the nonzero residue classes modulo $p$ form the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^\times$ of order $p-1$. In ring theory, prime numbers are the model example for [prime ideals](/page/Ideal): the ideal $(p) \trianglelefteq \mathbb{Z}$ is prime exactly when $p$ is a prime number. The quotient $\mathbb{Z}/(p)$ is then an [integral domain](/page/Integral%20Domain), and since it is finite, it is a [field](/page/Field). In arithmetic functions, prime factorisation supports definitions such as Euler's totient function $\varphi(n)$, the Mobius function $\mu(n)$, divisor sums $\sigma_k(n)$, and Dirichlet convolution. These functions are often multiplicative because the prime-power components of $n$ behave independently. In analytic number theory, primes become a sequence whose distribution is studied through counting functions. To ask how common primes are among the positive integers, one first records how many have appeared by a given size. [definition: Prime Counting Function] The prime counting function is the function $\pi: [0,\infty) \to \mathbb{N}\cup\{0\}$ defined by \begin{align*} \pi(x) = |\{p \in \mathbb{N} : p \text{ is prime and } p \le x\}|. \end{align*} [/definition] The prime counting function turns primes from individual divisibility objects into a sequence whose large-scale density can be measured. Small tables of primes suggest that gaps grow, but they do not reveal a stable law for the cumulative count $\pi(x)$. The [prime number theorem](/theorems/1692), developed later in analytic number theory, gives such a law: roughly, the number of primes up to $x$ is comparable to $x/\log x$ for large $x$. This result is far beyond the elementary definition of prime number, but it studies the same objects introduced by the divisor condition. ## References Euclid, *Elements* (c. 300 BCE). G. H. Hardy and E. M. Wright, *An Introduction to the Theory of Numbers* (1979). Tom M. Apostol, *Introduction to Analytic Number Theory* (1976). [Cambridge IA Numbers and Sets](/page/Cambridge%20IA%20Numbers%20and%20Sets). [Congruence](/page/Congruence). [Unique Factorisation Domain](/page/Unique%20Factorisation%20Domain).