Composite Number

A composite number is a positive integer which is not prime (i.e., which has factors other than 1 and itself). The first few composite numbers (sometimes called "composites" for short) are 4, 6, 8, 9, 10, 12, 14, 15, 16, ... (OEIS A002808), whose prime factorizations are summarized in the following table. Note that the number 1 is a special case which is considered to be neither composite nor prime.

	prime factorization		prime factorization
4		20
6		21
8		22
9		24
10		25
12		26
14		27
15		28
16		30
18		32

For , the th composite number can be generated using the Wolfram Language code

Composite[n_Integer] /; n >= 1 :=
 FixedPoint[n + PrimePi[#] + 1&, n]

The Dirichlet generating function of the characteristic function of the composite numbers is given for by

			(1)
			(2)
			(3)

where is the Riemann zeta function, is the prime zeta function, and is an Iverson bracket.

There are an infinite number of composite numbers.

The composite number problem asks whether a given positive integer can be written as with integers and .

A composite number can always be written as a product in at least two ways (since is always possible). For positive integers , , , and , call these two products

(4)

then it is obviously the case that ( divides ). Set

(5)

where is the greatest common divisor of and , and . Writing , the integers and are relatively prime, so divides . Put . Then

			(6)
			(7)

Solving for gives

(8)

It then follows that

			(9)
			(10)
			(11)

It therefore follows that is never prime! In fact, the more general result that

(12)

is never prime for an integer also holds (Honsberger 1991).