# Composite number
A composite number is a positive integer greater than 1 that is not prime, meaning it has factors other than 1 and itself; equivalently, it can be written as a product of two smaller whole numbers, each greater than 1[1](https://mathworld.wolfram.com/CompositeNumber.html). For example, 6 = 2 × 3 is composite, while 7 cannot be made by multiplying smaller whole numbers and is prime[2](https://www.mathsisfun.com/definitions/composite-number.html). The number 1 is a special case, considered neither prime nor composite[1](https://mathworld.wolfram.com/CompositeNumber.html), so every whole number above 1 is either composite or prime[2](https://www.mathsisfun.com/definitions/composite-number.html).
| Key fact | Detail |
|---|---|
| Definition | A positive integer n > 1 that is not prime, i.e. has factors other than 1 and itself[1](https://mathworld.wolfram.com/CompositeNumber.html) |
| First examples | 4, 6, 8, 9, 10, 12, 14, 15, 16, ... (OEIS A002808)[1](https://mathworld.wolfram.com/CompositeNumber.html) |
| Status of 1 | Neither prime nor composite[1](https://mathworld.wolfram.com/CompositeNumber.html) |
| Counting | The number of composites ≤ n is n − π(n) − 1, where π(n) counts primes ≤ n[3](https://oeis.org/A002808) |
| Infinitude | There are infinitely many composite numbers[1](https://mathworld.wolfram.com/CompositeNumber.html) |
| Runs of composites | For any positive integer n there exist n consecutive composite integers[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_%28Barrus_and_Clark%29/01%3A_Chapters/1.11%3A_Prime_Numbers) |
| Cryptographic role | RSA moduli are composite numbers, products of two primes p and q, with bit length at least 2048 in current US federal standards[5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf) |
## Definition and basic properties
The definition can be stated in two equivalent ways. In terms of multiplication, a composite number is a whole number that can be made by multiplying other whole numbers, excluding the trivial products 1 × n and n × 1[2](https://www.mathsisfun.com/definitions/composite-number.html). In terms of division, a number is composite when it can be divided exactly by a whole number other than 1 and itself; 12, for instance, is divisible by 1, 2, 3, 4, 6, and 12, so it has more factors than the two required of a prime[6](https://www.mathsisfun.com/prime-composite-number.html).
Every composite number has a unique decomposition into prime factors, called its prime factorization. The first composites and their decompositions are 4 = 2², 6 = 2·3, 8 = 2³, 9 = 3², 10 = 2·5, 12 = 2²·3, and so on[1](https://mathworld.wolfram.com/CompositeNumber.html). The name reflects the word "composite" in the sense of something made by combining things: composites are built by multiplying primes together[6](https://www.mathsisfun.com/prime-composite-number.html).
**Counting composites.** Because 1 is neither prime nor composite, the count of composite numbers up to n is n − π(n) − 1, where π(n) is the prime-counting function[3](https://oeis.org/A002808). The nth composite number cₙ satisfies cₙ = π(cₙ) + 1 + n, and bounds of the form n + n/log n + n/log²n < cₙ < n + n/log n + 3n/log²n hold for n ≥ 4[3](https://oeis.org/A002808). There are infinitely many composites, a consequence of the infinitude of primes together with the existence of arbitrarily long composite runs[1](https://mathworld.wolfram.com/CompositeNumber.html).
## Ancient origins
The concept appears in Book VII of Euclid's *Elements* (circa 300 BC), the first of his three books on number theory. Definition 13 states that "a composite number is that which is measured by some number," meaning a number divisible by some smaller number, while [Definition](https://www.edgepedia.org/definition) 11 defines a prime as measured by a unit alone[7](https://www.perseus.tufts.edu/hopper/text?doc=Euc.+7&fromdoc=Perseus%3Atext%3A1999.01.0086). Proposition 31 of the same book proves that any composite number is measured by some prime number, by repeatedly taking a smaller divisor until a prime is reached; the argument relies on the principle that a strictly decreasing sequence of numbers must terminate[8](https://www.euclids-elements.org/elements/books/bookVII/propositions/propVII31/). This result underlies the modern statement that every integer greater than 1 has a prime factor, and hence a prime factorization.
## Distribution among the integers
Composites dominate the natural numbers increasingly as numbers grow. The Prime Number Theorem, proved independently by [Jacques Hadamard](https://www.edgepedia.org/jacques-hadamard) and [Charles-Jean de la Vallée Poussin](https://www.edgepedia.org/charles-jean-de-la-vallee-poussin) in 1896, states that π(x) ∼ x/log x, so approximately 1/log n of the integers up to n are prime[9](https://www.math.uwaterloo.ca/~f2alfais/notes/pm340-notes.pdf). The complementary share, roughly n − n/log n, are composite (after accounting for 1), a fraction that approaches 1.
Given any positive integer n, one can find an integer a for which every one of the n successive integers a, a+1, ..., a+(n−1) is composite. The standard construction takes a = (n+1)! + 2: each term (n+1)! + i + 2 is divisible by i + 2, which lies between 2 and n+1 and is smaller than the term itself[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_%28Barrus_and_Clark%29/01%3A_Chapters/1.11%3A_Prime_Numbers). This shows that prime gaps can be made as long as desired, even though the Twin Prime Conjecture, which asserts infinitely many prime pairs differing by 2, remains unproven[4](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_%28Barrus_and_Clark%29/01%3A_Chapters/1.11%3A_Prime_Numbers).
## Recognizing composites: primality testing
Deciding whether a number is composite is computationally easier, in practice and in theory, than finding its factors. Most fast tests are probabilistic and are strictly compositeness tests: they prove compositeness when it holds but only give strong evidence of primality otherwise. The Miller-Rabin test, based on [Fermat's little theorem](https://www.edgepedia.org/fermats-little-theorem), has the property that any composite n, including Carmichael numbers such as 561 = 3 × 11 × 17 that fool the simpler Fermat test, passes a single random round with probability at most 1/4; repeated rounds reduce the error exponentially[10](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html).
A deterministic polynomial-time alternative arrived in 2004, when [Manindra Agrawal](https://www.edgepedia.org/manindra-agrawal), Neeraj Kayal, and [Nitin Saxena](https://www.edgepedia.org/nitin-saxena), all then at the Indian Institute of Technology Kanpur, published the [AKS primality test](https://www.edgepedia.org/aks-primality-test) in the *Annals of Mathematics*, an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite[11](https://annals.math.princeton.edu/2004/160-2/p12). The related decision problem, asking whether positive integers m and n exist with N = mn for a given N, is the composite number problem; its complexity was unknown for many years, although the problem was known to belong to NP ∩ co-NP[12](https://mathworld.wolfram.com/CompositeNumberProblem.html).
## Composites in cryptography
The security of RSA encryption rests on the gap between multiplying and factoring. Multiplying two large primes p and q to form the composite modulus n = pq is easy, but recovering p and q from n alone is extremely difficult, a property used to build practical encryption systems for electronic data[13](https://mathworld.wolfram.com/news/2005-05-10/rsa-200/). In the RSA digital signature scheme standardized by NIST in FIPS 186-5, the public key consists of a modulus n, the product of two positive prime integers p and q, together with a public exponent e, and the standard requires a modulus bit length of at least 2048 bits with p and q of equal bit length[5](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf).
The [RSA Factoring Challenge](https://www.edgepedia.org/rsa-factoring-challenge) published composite numbers, named by their digit counts, chosen specifically to be difficult to factor. In May 2005 a team at the German Federal Agency for Information Technology Security (BSI) announced the factorization of RSA-200, a 200-digit semiprime, by the same team that had earlier factored the 174-digit RSA-576[13](https://mathworld.wolfram.com/news/2005-05-10/rsa-200/). Such results measure the practical difficulty of factoring composites whose primality was never in doubt, since primality testing of the candidate factors is far cheaper than the factorization itself[13](https://mathworld.wolfram.com/news/2005-05-10/rsa-200/).
## Special families
Several named classes of composite numbers appear in number theory. A semiprime is a composite with exactly two prime factors, the form of every RSA challenge number[13](https://mathworld.wolfram.com/news/2005-05-10/rsa-200/). A Smith number is a composite number whose digit sum equals the sum of the digits of its prime factors excluding 1, and Rodney McDaniel showed in 1987 that there are infinitely many Smith numbers[14](https://mathworld.wolfram.com/SmithNumber.html). Highly composite numbers, composites with more divisors than any smaller positive integer, form another studied family[1](https://mathworld.wolfram.com/CompositeNumber.html).
Some composite numbers also carry structural identities: an integer n is composite if and only if σ(n) + φ(n) > 2n, where σ is the sum-of-divisors function and φ is [Euler's totient function](https://www.edgepedia.org/eulers-totient-function)[3](https://oeis.org/A002808), and every composite can be written as a sum of strictly positive integers in arithmetic progression with common difference 2, such as 4 = 1 + 3 and 9 = 1 + 3 + 5[3](https://oeis.org/A002808).
## References
1. [Weisstein, Eric W. "Composite Number." MathWorld--A Wolfram Resource.](https://mathworld.wolfram.com/CompositeNumber.html)
2. [Composite Number Definition, Illustrated Mathematics Dictionary, Math is Fun.](https://www.mathsisfun.com/definitions/composite-number.html)
3. [A002808: The composite numbers, The On-Line Encyclopedia of Integer Sequences.](https://oeis.org/A002808)
4. [Prime Numbers, Section 1.11, Elementary Number Theory (Barrus and Clark), Mathematics LibreTexts.](https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_%28Barrus_and_Clark%29/01%3A_Chapters/1.11%3A_Prime_Numbers)
5. [FIPS 186-5, Digital Signature Standard (DSS), NIST.](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)
6. [Prime Numbers and Composite Numbers, Math is Fun.](https://www.mathsisfun.com/prime-composite-number.html)
7. [Euclid, Elements, Book VII, Perseus Digital Library.](https://www.perseus.tufts.edu/hopper/text?doc=Euc.+7&fromdoc=Perseus%3Atext%3A1999.01.0086)
8. [Euclid's Elements, Book VII, Proposition 31.](https://www.euclids-elements.org/elements/books/bookVII/propositions/propVII31/)
9. [Lecture 7: The Distribution of Primes, PM 340 notes, University of Waterloo.](https://www.math.uwaterloo.ca/~f2alfais/notes/pm340-notes.pdf)
10. [Primality Tests: The Miller-Rabin Test, Stanford cryptography notes.](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html)
11. [Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES is in P." Annals of Mathematics 160(2): 781-793.](https://annals.math.princeton.edu/2004/160-2/p12)
12. [Weisstein, Eric W. "Composite Number Problem." MathWorld--A Wolfram Resource.](https://mathworld.wolfram.com/CompositeNumberProblem.html)
13. [Weisstein, Eric W. "MathWorld News: RSA-200 Factored" (May 10, 2005), MathWorld.](https://mathworld.wolfram.com/news/2005-05-10/rsa-200/)
14. [Weisstein, Eric W. "Smith Number." MathWorld--A Wolfram Resource.](https://mathworld.wolfram.com/SmithNumber.html)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Analytic number theory › Primes and factorization*
*Initially written Sep 17, 2026 · Reviewed: Sep 17, 2026; Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license