View source for Composite number

{{Short description|Integer having a non-trivial divisor}}
[[File:Composite number Cuisenaire rods 10.svg|thumb|Demonstration, with [[Cuisenaire rods]], of the divisors of the composite number 10]]
[[File:Primes-vs-composites.svg | thumb|right | Composite numbers can be arranged into [[rectangles]] but prime numbers cannot.|alt=Groups of two to twelve dots, showing that the composite numbers of dots (4, 6, 8, 9, 10, and 12) can be arranged into rectangles but prime numbers cannot]]

A '''composite number''' is a [[positive integer]] that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one [[divisor]] other than 1 and itself.{{sfn|Pettofrezzo|Byrkit|1970|pp=23–24}}{{sfn|Long|1972|p=16}} Every positive integer is composite, [[prime number|prime]], or the [[Unit (ring theory)|unit]]&nbsp;1, so the composite numbers are exactly the numbers that are not prime and not a unit.{{sfn|Fraleigh|1976|pp=198,266}}{{sfn|Herstein|1964|p=106}}

For example, the integer 14 is a composite number because it is the product of the two smaller integers 2&nbsp;&times;&nbsp;7. But the integers 2 and 3 are not composite numbers because each of them can only be divided by one and itself.

The composite numbers up to 150 are:
:4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 102, 104, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 128, 129, 130, 132, 133, 134, 135, 136, 138, 140, 141, 142, 143, 144, 145, 146, 147, 148, 150. {{OEIS|id=A002808}}

Every composite number can be written as the product of two or more (not necessarily distinct) primes.{{sfn|Long|1972|p=16}} For example, the composite number [[299 (number)|299]] can be written as 13 × 23, and the composite number [[360 (number)|360]] can be written as 2<sup>3</sup> × 3<sup>2</sup> × 5; furthermore, this representation is unique [[up to]] the order of the factors. This fact is called the [[fundamental theorem of arithmetic]].{{sfn|Fraleigh|1976|p=270}}{{sfn|Long|1972|p=44}}{{sfn|McCoy|1968|p=85}}{{sfn|Pettofrezzo|Byrkit|1970|p=53}}

There are several known [[primality test]]s that can determine whether a number is prime or composite, without necessarily revealing the factorization of a composite input.

==Types==

One way to classify composite numbers is by counting the number of prime factors. A composite number with two prime factors is a [[semiprime]] or 2-almost prime (the factors need not be distinct, hence squares of primes are included). A composite number with three distinct prime factors is a [[sphenic number]]. In some applications, it is necessary to differentiate between composite numbers with an odd number of distinct prime factors and those with an even number of distinct prime factors. For the latter 
:<math>\mu(n) = (-1)^{2x} = 1</math>

(where μ is the [[Möbius function]] and ''x'' is half the total of prime factors), while for the former

:<math>\mu(n) = (-1)^{2x + 1} = -1.</math>

However, for prime numbers, the function also returns −1 and <math>\mu(1) = 1</math>. For a number ''n'' with one or more repeated prime factors,

:<math>\mu(n) = 0</math>.{{sfn|Long|1972|p=159}}

If ''all'' the prime factors of a number are repeated it is called a [[powerful number]] (All [[perfect power]]s are powerful numbers). If ''none'' of its prime factors are repeated, it is called [[Square-free integer|squarefree]]. (All prime numbers and 1 are squarefree.)

For example, [[72 (number)|72]] = 2<sup>3</sup> × 3<sup>2</sup>, all the prime factors are repeated, so 72 is a powerful number. [[42 (number)|42]] = 2 × 3 × 7, none of the prime factors are repeated, so 42 is squarefree.

{{Euler_diagram_numbers_with_many_divisors.svg}}
Another way to classify composite numbers is by counting the number of divisors. All composite numbers have at least three divisors. In the case of squares of primes, those divisors are <math>\{1, p, p^2\}</math>. A number ''n'' that has more divisors than any ''x'' < ''n'' is a [[highly composite number]] (though the first two such numbers are 1 and 2).

Composite numbers have also been called "rectangular numbers", but that name can also refer to the [[pronic number]]s, numbers that are the product of two consecutive integers.

Yet another way to classify composite numbers is to determine whether all prime factors are either all below or all above some fixed (prime) number. Such numbers are called [[smooth number]]s and [[rough number]]s, respectively.

==See also==
{{portal|Mathematics}}
* [[Canonical representation of a positive integer]]
* [[Integer factorization]]
* [[Sieve of Eratosthenes]]
* [[Table of prime factors]]

==Notes==
{{reflist}}

==References==
* {{ citation | first1 = John B. | last1 = Fraleigh | year = 1976 | isbn = 0-201-01984-1 | title = A First Course In Abstract Algebra | edition = 2nd | publisher = [[Addison-Wesley]] | location = Reading }}
* {{ citation | first1 = I. N. | last1 = Herstein | author-link=Israel Nathan Herstein | year = 1964 | isbn = 978-1114541016 | title = Topics In Algebra | publisher = [[Blaisdell Publishing Company]] | location = Waltham }}
* {{ citation | first1 = Calvin T. | last1 = Long | year = 1972 | title = Elementary Introduction to Number Theory | edition = 2nd | publisher = [[D. C. Heath and Company]] | location = Lexington | lccn = 77-171950 }}
* {{ citation | first1 = Neal H. | last1 = McCoy | year = 1968 | title = Introduction To Modern Algebra, Revised Edition | publisher = [[Allyn and Bacon]] | location = Boston | lccn = 68-15225 }}
* {{ citation | first1 = Anthony J. | last1 = Pettofrezzo | first2 = Donald R. | last2 = Byrkit | year = 1970 | title = Elements of Number Theory | publisher = [[Prentice Hall]] | location = Englewood Cliffs | lccn = 77-81766 }}

== External links ==
* [http://naturalnumbers.org/composites.html Lists of composites with prime factorization (first 100, 1,000, 10,000, 100,000, and 1,000,000)]
* [http://www.divisorplot.com/index.html Divisor Plot (patterns found in large composite numbers)]

{{Classes of natural numbers}}
{{Divisor classes}}

[[Category:Prime numbers| Composite]]
[[Category:Integer sequences]]
[[Category:Arithmetic]]
[[Category:Elementary number theory]]