composite number

A positive integer n which can be factored into smaller positive integers (n=ab), neither of which is one, is a composite. This means that the positive integers can be divided into the three disjoint classes:

1. the unit {1},
2. the primes {2, 3, 5, 7, 11, 13, 17, ...},
3. and the composites {4, 6, 8, 9, 10, 12, ...}.

How do we recognize if n is a composite number? One way is to find a proper divisor. If n is small, then we can do this by dividing it by the primes up to the square root of n. When n is larger, we can use one of the classical primality tests or modern tests (such as ECPP or CYCLOTOMY). See the pages on primality proving linked below.

Why do we care? One reason is that many secret codes (e.g., RSA) and much of the security of the Internet (e.g., PGP) depends in part on the relative difficulty of factoring large numbers. But more basic to a mathematician is that this problem has always been central to number theory. Gauss put it this way:

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated. (Carl Friedrich Gauss, Disquisitiones Arithmeticae, 1801)

Related pages (outside of this work)

• How to find primes and prove primality