A composite number is a positive integer greater than 1 that can be expressed as the product of two smaller positive integers. Equivalently, it has a positive divisor other than 1 and itself. Composite numbers contrast with prime numbers, which have exactly two positive divisors. Every integer greater than 1 belongs to exactly one of these two classes. Their distinction is fundamental to number theory.
Definition and examples
An integer is composite if there exist integers and such that
The first composite numbers are
For example, , so 12 is composite. Its positive divisors are . The number 9 is composite because : the two factors need not be distinct.
The smallest composite number is 4. Every even integer greater than 2 is composite because it is divisible by 2, but composites can also be odd, as 9, 15, and 25 demonstrate.
The number 1 is neither prime nor composite, since it has only one positive divisor. Zero and negative integers are also excluded from the standard definition. Whether a convention includes zero among the natural numbers does not affect this classification.
Prime factorization
The fundamental theorem of arithmetic states that every integer greater than 1 has a factorization into primes that is unique apart from the order of its factors. Thus any such integer can be written as
where the are distinct primes and the are positive integers.
The number is composite precisely when
This counts prime factors with multiplicity. For example,
has five prime factors counted with multiplicity, but only two distinct prime factors.
The number of positive divisors of , usually denoted by , is
Each divisor is obtained by independently choosing an exponent between 0 and for each prime . Consequently, an integer greater than 1 is composite exactly when it has more than two positive divisors.
Important types
Several classes describe the factorization structure of composite numbers:
- A semiprime is a product of exactly two primes, counted with multiplicity. Examples include , , and .
- A prime power has the form , with prime. It is composite when .
- A squarefree composite number has no repeated prime factor. For example, is squarefree, whereas is not.
These classes overlap: 6 is both semiprime and squarefree, while 9 is both semiprime and a prime power.
Detecting compositeness
Trial division
Every composite integer has a prime divisor no greater than . To see this, write with . Then , so ; at least one prime divisor of is therefore also no greater than .
This gives a basic test: divide by each prime not exceeding . Finding any such divisor proves that is composite. If none divides , then is prime.
For example, to test 91, only the primes 2, 3, 5, and 7 need consideration. Since , it is composite.
Trial division is effective for small numbers but becomes expensive for large inputs. Its worst-case running time grows exponentially in the number of digits of the input.
Sieving and primality tests
The sieve of Eratosthenes identifies primes up to a chosen bound by marking composite numbers as multiples of smaller primes. When processing a prime , marking can begin at , because smaller multiples of already have smaller prime factors.
For large individual integers, primality tests can determine whether a number is prime without finding its factors. Many use modular arithmetic. A failed necessary condition for primality proves compositeness; passing a particular test need not prove primality unless that test provides a conclusive criterion.
Establishing that a number is composite and finding its factors are distinct computational tasks. A test can demonstrate compositeness without revealing a nontrivial divisor.
Distribution
There are infinitely many composite numbers: the even integers greater than 2 already form an infinite family.
There are also arbitrarily long runs of consecutive composite integers. For any integer , consider
where the exclamation mark denotes a factorial. Each term is divisible by and greater than , so these are consecutive composite numbers. This construction proves the existence of long runs, but generally does not produce the earliest such run.
Composite numbers have natural density 1 among the positive integers. If counts the primes not exceeding , the number of composites not exceeding , for , is
The prime number theorem gives , so the proportion of integers up to that are composite tends to 1 as increases. This does not mean that primes eventually stop occurring.
Historical and computational significance
The distinction between prime and composite numbers appears in ancient Greek mathematics. Book VII of Euclid’s *Elements* defines a composite number as one measured by some number, using “measured” in the sense of exact divisibility.
In modern computation, integer factorization concerns decomposing an integer into factors, ultimately into primes. Multiplying known factors is computationally straightforward, whereas factoring a sufficiently large product of suitably chosen primes can be much harder with known classical methods.
This distinction underlies RSA, whose public modulus is typically the product of two large distinct primes. Factoring that modulus permits recovery of the private key in standard RSA. Compositeness alone does not imply computational difficulty: integers with small prime factors or special algebraic structure may be easy to factor.