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

with

Thus a composite number can be factored into smaller positive integers.

For example,

Hence $4$, $6$, and $12$ are composite numbers.

A composite integer therefore possesses at least one nontrivial divisor.

Prime and Composite Integers

Every integer greater than $1$ is either prime or composite, but never both.

A prime number has exactly two positive divisors:

A composite number has more than two positive divisors.

For example, the divisors of $12$ are

Since there are divisors other than $1$ and $12$, the integer $12$ is composite.

The integer $1$ is neither prime nor composite.

Small Composite Numbers

The first few composite numbers are

The smallest composite number is

Every even integer greater than $2$ is composite because it is divisible by $2$.

For example,

Odd integers may also be composite:

Thus parity alone does not determine primality.

Nontrivial Divisors

A divisor $d$ of $n$ is called nontrivial if

An integer $n>1$ is composite exactly when it possesses a nontrivial divisor.

For example, $15$ has nontrivial divisors

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,

and

Hence

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,

while

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

observe that

Hence $91$ is composite.

A useful fact is that if $n$ is composite, then it has a divisor $d$ satisfying

Indeed, if

and both $a$ and $b$ exceeded $\sqrt n$, then

which is impossible.

Thus primality testing requires checking divisors only up to

Even and Odd Composite Numbers

Composite numbers may be classified by parity.

Even Composite Numbers

Every even integer greater than $2$ is composite. Indeed,

for some integer $k>1$.

Examples include

Odd Composite Numbers

Odd composite numbers are not divisible by $2$, but they possess other divisors.

Examples include

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,

has divisors

while

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

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.