Composite numbers are positive integers greater than 1 that are divisible by numbers other than 1 and themselves. In other words, a composite n has a factor d with 1 < d < n. The sequence of composite numbers begins 4, 6, 8, 9, 10, 12, ... and includes many familiar integers formed by multiplying smaller integers.
Definition and basic properties
Formally, an integer n > 1 is composite when it can be written as n = a·b with integers a, b > 1. Numbers that are not composite and are greater than 1 are called primes. The number 1 is neither prime nor composite; 0 and negative integers are not considered in the usual classification of natural-number primality.
Prime factorization
Every composite number can be expressed as a product of prime numbers. This factorization is unique up to the order of the prime factors; this statement is known as the fundamental theorem of arithmetic. Typical examples illustrate common patterns:
- 4 = 2 × 2 (a prime power)
- 6 = 2 × 3 (product of two distinct primes)
- 12 = 2 × 2 × 3 (contains repeated prime factors)
- 9 = 3 × 3 (square of a prime)
Special classes and distinctions
Within composites there are several useful subcategories: semiprimes (product of exactly two primes, not necessarily distinct), prime powers (p^k for k >= 2), and squarefree composites (products of distinct primes). A number is composite precisely when it is not prime and exceeds 1.
Testing for compositeness
To show a number is composite it suffices to find a nontrivial divisor. Elementary methods use trial division by primes up to the square root of the number. For very large integers, algorithmic tests and probabilistic methods (for example Miller–Rabin) and deterministic algorithms (including AKS) are employed in computational number theory; such tests are central to distinguishing primes from composites in practice.
History and applications
The concepts of prime and composite integers date back to ancient mathematics and form the foundation of elementary number theory. The hardness of factoring large composite numbers into their prime factors underpins modern public-key cryptography systems: cryptographic security often relies on it being computationally difficult to recover prime factors of certain composite integers. For introductions and deeper treatments, see further reading or algorithmic sources such as computational number theory guides.
Notable fact: because every composite has a prime factor no greater than its square root, finding a small divisor is a common practical approach. Understanding composites and their factorization remains a central theme in both pure and applied mathematics.