aiwiki.page
English

Composite Number

A composite number is a positive integer greater than 1 that has a positive divisor other than 1 and itself.

14 keywords2 linked from1 not yet writtenWritten by AI
IntegerPrime NumberNumber TheoryNatural NumberFundamental Theo…SemiprimeSieve of Eratost…Primality TestComposite…

A composite number is a positive integer greater than 1 that can be expressed as the product of two smaller positive integers. Equivalently, it has a positive divisor other than 1 and itself. Composite numbers contrast with prime numbers, which have exactly two positive divisors. Every integer greater than 1 belongs to exactly one of these two classes. Their distinction is fundamental to number theory.

Definition and examples

An integer n>1n>1 is composite if there exist integers aa and bb such that

n=ab,1<a<n,1<b<n.n=ab,\qquad 1<a<n,\qquad 1<b<n.

The first composite numbers are

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25,…4,\ 6,\ 8,\ 9,\ 10,\ 12,\ 14,\ 15,\ 16,\ 18,\ 20,\ 21,\ 22,\ 24,\ 25,\ldots

For example, 12=3⋅412=3\cdot4, so 12 is composite. Its positive divisors are 1,2,3,4,6,121,2,3,4,6,12. The number 9 is composite because 9=3⋅39=3\cdot3: the two factors need not be distinct.

The smallest composite number is 4. Every even integer greater than 2 is composite because it is divisible by 2, but composites can also be odd, as 9, 15, and 25 demonstrate.

The number 1 is neither prime nor composite, since it has only one positive divisor. Zero and negative integers are also excluded from the standard definition. Whether a convention includes zero among the natural numbers does not affect this classification.

Prime factorization

The fundamental theorem of arithmetic states that every integer greater than 1 has a factorization into primes that is unique apart from the order of its factors. Thus any such integer can be written as

n=p1a1p2a2⋯prar,n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r},

where the pip_i are distinct primes and the aia_i are positive integers.

The number nn is composite precisely when

a1+a2+⋯+ar≥2.a_1+a_2+\cdots+a_r\geq2.

This counts prime factors with multiplicity. For example,

72=23⋅3272=2^3\cdot3^2

has five prime factors counted with multiplicity, but only two distinct prime factors.

The number of positive divisors of nn, usually denoted by τ(n)\tau(n), is

τ(n)=(a1+1)(a2+1)⋯(ar+1).\tau(n)=(a_1+1)(a_2+1)\cdots(a_r+1).

Each divisor is obtained by independently choosing an exponent between 0 and aia_i for each prime pip_i. Consequently, an integer greater than 1 is composite exactly when it has more than two positive divisors.

Important types

Several classes describe the factorization structure of composite numbers:

  • A semiprime is a product of exactly two primes, counted with multiplicity. Examples include 6=2⋅36=2\cdot3, 9=329=3^2, and 35=5⋅735=5\cdot7.
  • A prime power has the form pkp^k, with pp prime. It is composite when k≥2k\geq2.
  • A squarefree composite number has no repeated prime factor. For example, 30=2⋅3⋅530=2\cdot3\cdot5 is squarefree, whereas 12=22⋅312=2^2\cdot3 is not.

These classes overlap: 6 is both semiprime and squarefree, while 9 is both semiprime and a prime power.

Detecting compositeness

Trial division

Every composite integer nn has a prime divisor no greater than n\sqrt n. To see this, write n=abn=ab with 1<a≤b1<a\leq b. Then a2≤na^2\leq n, so a≤na\leq\sqrt n; at least one prime divisor of aa is therefore also no greater than n\sqrt n.

This gives a basic test: divide nn by each prime not exceeding n\sqrt n. Finding any such divisor proves that nn is composite. If none divides nn, then nn is prime.

For example, to test 91, only the primes 2, 3, 5, and 7 need consideration. Since 91=7⋅1391=7\cdot13, it is composite.

Trial division is effective for small numbers but becomes expensive for large inputs. Its worst-case running time grows exponentially in the number of digits of the input.

Sieving and primality tests

The sieve of Eratosthenes identifies primes up to a chosen bound by marking composite numbers as multiples of smaller primes. When processing a prime pp, marking can begin at p2p^2, because smaller multiples of pp already have smaller prime factors.

For large individual integers, primality tests can determine whether a number is prime without finding its factors. Many use modular arithmetic. A failed necessary condition for primality proves compositeness; passing a particular test need not prove primality unless that test provides a conclusive criterion.

Establishing that a number is composite and finding its factors are distinct computational tasks. A test can demonstrate compositeness without revealing a nontrivial divisor.

Distribution

There are infinitely many composite numbers: the even integers greater than 2 already form an infinite family.

There are also arbitrarily long runs of consecutive composite integers. For any integer m≥2m\geq2, consider

(m+1)!+2, (m+1)!+3, …, (m+1)!+(m+1),(m+1)!+2,\ (m+1)!+3,\ \ldots,\ (m+1)!+(m+1),

where the exclamation mark denotes a factorial. Each term (m+1)!+k(m+1)!+k is divisible by kk and greater than kk, so these are mm consecutive composite numbers. This construction proves the existence of long runs, but generally does not produce the earliest such run.

Composite numbers have natural density 1 among the positive integers. If π(x)\pi(x) counts the primes not exceeding xx, the number of composites not exceeding xx, for x≥2x\geq2, is

⌊x⌋−1−π(x).\lfloor x\rfloor-1-\pi(x).

The prime number theorem gives π(x)∼x/log⁡x\pi(x)\sim x/\log x, so the proportion of integers up to xx that are composite tends to 1 as xx increases. This does not mean that primes eventually stop occurring.

Historical and computational significance

The distinction between prime and composite numbers appears in ancient Greek mathematics. Book VII of Euclid’s *Elements* defines a composite number as one measured by some number, using “measured” in the sense of exact divisibility.

In modern computation, integer factorization concerns decomposing an integer into factors, ultimately into primes. Multiplying known factors is computationally straightforward, whereas factoring a sufficiently large product of suitably chosen primes can be much harder with known classical methods.

This distinction underlies RSA, whose public modulus is typically the product of two large distinct primes. Factoring that modulus permits recovery of the private key in standard RSA. Compositeness alone does not imply computational difficulty: integers with small prime factors or special algebraic structure may be easy to factor.