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

$$ 1<a<n, \qquad 1<b<n. $$

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

For example,

$$ 4=2\cdot2, \qquad 6=2\cdot3, \qquad 12=3\cdot4. $$

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:

$$ 1 \quad\text{and itself}. $$

A composite number has more than two positive divisors.

For example, the divisors of $12$ are

$$ 1,2,3,4,6,12. $$

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

$$ 4,6,8,9,10,12,14,15,16,\ldots $$

The smallest composite number is

$$ 4=2^2. $$

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

For example,

$$ 18=2\cdot9, \qquad 100=2\cdot50. $$

Odd integers may also be composite:

$$ 9=3^2, \qquad 21=3\cdot7. $$

Thus parity alone does not determine primality.

Nontrivial Divisors

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

$$ 1<d<n. $$

An integer $n>1$ 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.