最初の 200 個の合成数

The split between prime and composite is as old as Greek arithmetic. Book VII of Euclid's Elements, from about 300 BCE, defines a composite number as one that is measured by some number — that is, one with a divisor other than itself and 1. Nicomachus of Gerasa went further around the start of the second century CE: his Introduction to Arithmetic sorts the odd numbers into the prime and incomposite, the secondary and composite, and a third class that is composite in itself yet prime in relation to another number. Classification rather than computation was the point, since the Pythagorean tradition he wrote in treated arithmetic as a branch of metaphysics.

The practical tool for composites was the sieve credited to Eratosthenes, which tests nothing: it strikes out multiples and lets the primes survive, so what it actually enumerates is the composites. Fibonacci's Liber Abaci of 1202 added the observation that saves most of the work in checking a single number — trial division can stop at the square root, because a composite n must have a factor no larger than √n.

Attention later turned from listing composites to certifying them without factoring. Fermat's little theorem gives a cheap test, and the test has liars: Václav Šimerka published the first seven of them — 561, 1105, 1729, 2465, 2821, 6601 and 8911 — in a Czech journal in 1885, where the result went unnoticed. Robert Carmichael described the same numbers independently in 1910, Nicolaas Beeger attached Carmichael's name to them in 1950, and Alford, Granville and Pomerance proved in 1994 that infinitely many exist.

Ramanujan took the opposite tack in a paper of 1915 on numbers with more divisors than any smaller number: the highly composite numbers 1, 2, 4, 6, 12, 24, 36, 48, 60, 120 and onwards. Jean-Pierre Kahane later suggested that Plato picked 5040 as his ideal city's population because it is one of them — an argument about Plato, not a theorem.

主な性質

• 4 is the smallest composite number. 1 is neither prime nor composite, since it has only one divisor.
• Every composite n has a prime factor no larger than √n, which is why trial division can stop at the square root.
• There are 74 composite numbers from 1 to 100: the hundred integers, less the 25 primes, less 1.
• Composites have density 1 — by the prime number theorem the share of integers up to x that are composite tends to 100%.
• From 4 upwards, consecutive composites are never more than 2 apart, because two consecutive integers above 2 cannot both be prime.
• Runs of composites are nevertheless arbitrarily long: for any n, the n numbers (n+1)!+2, (n+1)!+3, …, (n+1)!+(n+1) are all composite.
• A semiprime is a composite with exactly two prime factors counted with multiplicity: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, … (12 = 2² × 3 has three, so it is not one).
• A Carmichael number is a composite that passes the Fermat primality test for every base coprime to it. The smallest is 561 = 3 × 11 × 17.