# Composite Numbers ## Definition of Composite Numbers A positive integer $n>1$ is called composite if it is not prime. Equivalently, $n$ is composite if there exist integers $a$ and $b$ such that $$ n=ab, $$ with $$ 11$ is composite exactly when it possesses a nontrivial divisor. For example, $15$ has nontrivial divisors $$ 3 \quad\text{and}\quad 5. $$ The existence of nontrivial divisors distinguishes composite numbers from primes. ## Composite Numbers and Factorization Every composite integer can be decomposed into smaller factors. If these smaller factors are composite, the process may continue. For example, $$ 84=2\cdot42 $$ and $$ 42=2\cdot21, \qquad 21=3\cdot7. $$ Hence $$ 84=2^2\cdot3\cdot7. $$ This process eventually terminates because each step reduces the size of the factors. The final result is a factorization into prime numbers. ## Prime Factorization of Composite Numbers Every composite number can be written as a product of primes. For example, $$ 60=2^2\cdot3\cdot5, $$ while $$ 90=2\cdot3^2\cdot5. $$ This factorization is unique up to ordering of the prime factors. The existence and uniqueness of prime factorization form the content of the fundamental theorem of arithmetic. Composite numbers therefore derive their structure entirely from primes. ## Detecting Composite Numbers To determine whether $n$ is composite, it suffices to find a nontrivial divisor. For example, to test $$ 91, $$ observe that $$ 91=7\cdot13. $$ Hence $91$ is composite. A useful fact is that if $n$ is composite, then it has a divisor $d$ satisfying $$ 2\le d\le\sqrt n. $$ Indeed, if $$ n=ab $$ and both $a$ and $b$ exceeded $\sqrt n$, then $$ ab>n, $$ which is impossible. Thus primality testing requires checking divisors only up to $$ \sqrt n. $$ ## Even and Odd Composite Numbers Composite numbers may be classified by parity. ### Even Composite Numbers Every even integer greater than $2$ is composite. Indeed, $$ n=2k $$ for some integer $k>1$. Examples include $$ 4,6,8,10,12. $$ ### Odd Composite Numbers Odd composite numbers are not divisible by $2$, but they possess other divisors. Examples include $$ 9=3^2, \qquad 15=3\cdot5, \qquad 25=5^2. $$ Odd composite numbers are often more difficult to analyze because their factors are less immediately visible. ## Highly Composite Numbers Some integers possess unusually many divisors. For example, $$ 12 $$ has divisors $$ 1,2,3,4,6,12, $$ while $$ 24 $$ has eight positive divisors. Such integers are called highly composite numbers when they possess more divisors than any smaller positive integer. Questions about divisor counts lead naturally to arithmetic functions and multiplicative number theory. ## Composite Numbers in Number Theory Composite numbers are important not merely because they are nonprime, but because their structure reflects the arithmetic interaction of primes. Many number-theoretic questions concern the factorization of composite integers: - determining prime divisors, - counting divisors, - studying greatest common divisors, - solving congruences, - factoring large integers computationally. Modern cryptography relies heavily on the difficulty of factoring large composite numbers. In systems such as RSA, one works with integers of the form $$ n=pq, $$ where $p$ and $q$ are large primes. Although multiplication is computationally easy, recovering the prime factors of a large composite integer can be extremely difficult. Thus composite numbers stand at the intersection of elementary arithmetic, algebraic structure, and computational complexity.