Composite Number
A composite number is a whole number greater than 1 that has more than two factors, meaning it can be divided by numbers other than 1 and itself.
Definition
A composite number is a counting number greater than $1$ that can be divided evenly by at least one other number besides $1$ and itself, meaning it has more than two factors. Equivalently, a composite number $n > 1$ can be written as a product of two integers each greater than $1$, and has at least one factor $d$ where $1 < d < n$; the smallest prime factor of any composite $n$ is at most $\sqrt{n}$. In ring theory more generally, a composite element is one that is reducible, expressible as a product of two non-unit, non-zero elements, and the distinction between prime and irreducible elements (which coincide in UFDs but not in general rings) is central to algebraic number theory.
Example
$12$ is composite because you can divide it by $1$, $2$, $3$, $4$, $6$, and $12$, six factors in all. To test whether $97$ is prime, check primes up to $\sqrt{97} \approx 9.8$ (namely $2, 3, 5, 7$): none divide it, so $97$ is prime, whereas $91 = 7 \times 13$ is composite. Carmichael numbers, like $561 = 3 \times 11 \times 17$, are composite numbers that pass Fermat's primality test for all bases coprime to them, showing why Fermat's test alone is insufficient for primality certification.
Key Insight
If a number greater than $1$ is not prime, it is composite, and every composite number can be broken down into prime pieces. Needing to check only up to $\sqrt{n}$ makes the Sieve of Eratosthenes and trial division efficient for moderate-sized numbers. Most primality tests used in cryptography (like Miller-Rabin) are probabilistic rather than deterministic, because deterministic proofs of primality are slower; the AKS algorithm (2002) was the first polynomial-time deterministic primality test.