A composite number is a positive integer that has at least one divisor other than 1 and itself, meaning it can be formed by multiplying two smaller positive integers. Composite numbers are exactly those positive integers that are not prime and not the unit 1. For example, 14 is composite because it equals 2 × 7, while 2 and 3 are prime. Every composite number can be expressed uniquely as a product of primes, a fact known as the fundamental theorem of arithmetic. There are also various primality tests to determine if a number is prime or composite without revealing its factorization. The sequence of composite numbers up to 150 is listed in the OEIS.
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
μ ( n ) = ( − 1 ) 2 x = 1 {\displaystyle \mu (n)=(-1)^{2x}=1}(where μ is the Möbius function and x is half the total of prime factors), while for the former
μ ( n ) = ( − 1 ) 2 x + 1 = − 1. {\displaystyle \mu (n)=(-1)^{2x+1}=-1.}However, for prime numbers, the function also returns −1 and μ ( 1 ) = 1 {\displaystyle \mu (1)=1} . For a number n with one or more repeated prime factors,
μ ( n ) = 0 {\displaystyle \mu (n)=0} .10If all the prime factors of a number are repeated it is called a powerful number (All perfect powers are powerful numbers). If none of its prime factors are repeated, it is called squarefree. (All prime numbers and 1 are squarefree.)
For example, 72 = 23 × 32, all the prime factors are repeated, so 72 is a powerful number. 42 = 2 × 3 × 7, none of the prime factors are repeated, so 42 is squarefree.
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 { 1 , p , p 2 } {\displaystyle \{1,p,p^{2}\}} . 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 numbers, 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 numbers and rough numbers, respectively.
See also
- Mathematics portal
- Canonical representation of a positive integer
- Integer factorization
- Sieve of Eratosthenes
- Table of prime factors
Notes
- Fraleigh, John B. (1976), A First Course In Abstract Algebra (2nd ed.), Reading: Addison-Wesley, ISBN 0-201-01984-1
- Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN 978-1114541016
- Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950
- McCoy, Neal H. (1968), Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, LCCN 68-15225
- Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766
External links
- Lists of composites with prime factorization (first 100, 1,000, 10,000, 100,000, and 1,000,000)
- Divisor Plot (patterns found in large composite numbers)
References
Pettofrezzo & Byrkit 1970, pp. 23–24. - Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766 https://lccn.loc.gov/77-81766 ↩
Long 1972, p. 16. - Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950 https://lccn.loc.gov/77-171950 ↩
Fraleigh 1976, pp. 198, 266. - Fraleigh, John B. (1976), A First Course In Abstract Algebra (2nd ed.), Reading: Addison-Wesley, ISBN 0-201-01984-1 ↩
Herstein 1964, p. 106. - Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN 978-1114541016 ↩
Long 1972, p. 16. - Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950 https://lccn.loc.gov/77-171950 ↩
Fraleigh 1976, p. 270. - Fraleigh, John B. (1976), A First Course In Abstract Algebra (2nd ed.), Reading: Addison-Wesley, ISBN 0-201-01984-1 ↩
Long 1972, p. 44. - Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950 https://lccn.loc.gov/77-171950 ↩
McCoy 1968, p. 85. - McCoy, Neal H. (1968), Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, LCCN 68-15225 https://lccn.loc.gov/68-15225 ↩
Pettofrezzo & Byrkit 1970, p. 53. - Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766 https://lccn.loc.gov/77-81766 ↩
Long 1972, p. 159. - Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950 https://lccn.loc.gov/77-171950 ↩