Composite Number
ArithmeticA 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. It has more than two factors.
Example
$12$ is composite because you can divide it by $1$, $2$, $3$, $4$, $6$, and $12$. It has six factors.
Key Insight
If a number greater than $1$ is not prime, it is composite. Every composite number can be broken down into prime pieces.
Definition
A composite number $n > 1$ has at least one factor $d$ where $1 < d < n$. Equivalently, it can be written as a product of two integers each greater than $1$. The smallest prime factor of any composite $n$ is at most $\sqrt{n}$.
Example
To test if $97$ is prime: check primes up to $\sqrt{97} \approx 9.8$ (i.e., $2, 3, 5, 7$). None divide $97$, so $97$ is prime. Testing $91$: $7 \times 13 = 91$, so $91$ is composite.
Key Insight
The fact that you only need to check up to $\sqrt{n}$ for prime testing makes the Sieve of Eratosthenes and trial division efficient for moderate-sized numbers.
Definition
In a commutative ring, a composite element is one that is reducible: expressible as a product of two non-unit, non-zero elements. The distinction between prime and irreducible elements (which coincide in UFDs but not in general rings) is central to algebraic number theory.
Example
Carmichael numbers (e.g., $561 = 3 \times 11 \times 17$) are composite numbers that pass Fermat's primality test for all bases coprime to them. They demonstrate why Fermat's test alone is insufficient for primality certification.
Key Insight
Most primality tests in cryptography are probabilistic (Miller-Rabin) rather than deterministic because deterministic proofs of primality are slower. The AKS algorithm (2002) was the first polynomial-time deterministic primality test.