Составные числа

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.

Где встречаются

• An RSA public key is a composite semiprime. RSA-129, set as a challenge in Martin Gardner's Scientific American column of August 1977, held out until April 1994, when a 600-volunteer effort factored it; by 2015 the same number fell in about a day for roughly $30 of cloud time.
• Highly composite counts make division easy, which is why 12, 60 and 360 survive in clocks, angles and the sexagesimal arithmetic of Babylonian astronomy. That is a convention chosen for convenience, not a mathematical necessity.
• The fast Fourier transform is fastest when the input length is highly composite — a power of two ideally. Prime lengths need a different algorithm, such as Rader's or Bluestein's.
• Carmichael numbers are the reason production software uses Miller–Rabin or Baillie–PSW instead of a plain Fermat test: a Carmichael number slips past the Fermat test for every base coprime to it.
• 1729, the third Carmichael number, is also the Hardy–Ramanujan number: the smallest integer expressible as a sum of two positive cubes in two ways, 1³ + 12³ = 9³ + 10³.