Misplaced Pages

Composite number: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editContent deleted Content addedVisualWikitext
Revision as of 21:49, 13 May 2008 editHayson1991 (talk | contribs)242 editsm Kinds of composite numbers← Previous edit Latest revision as of 07:21, 14 December 2024 edit undoIStalingrad (talk | contribs)33 editsm Fixed spellingTag: Visual edit 
Line 1: Line 1:
{{Short description|Integer having a non-trivial divisor}}
{{Divisor_classes}}
], of the divisors of the composite number 10]]
A '''composite number''' is a ] ] which has a positive ] other than one or itself. In other words, if 0 < ''n'' is an integer and there are integers 1 < ''a'', ''b'' < ''n'' such that ''n'' = ''a'' × ''b'' then ''n'' is composite. By definition, every integer greater than ] is either a ] or a composite number. The number ] is a ] - it is neither prime nor composite. For example, the integer 14 is a composite number because it can be factored as 2&nbsp;&times;&nbsp;7.
] 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 ] that can be formed by multiplying two smaller positive integers. Accordingly it is a positive integer that has at least one ] other than 1 and itself.{{sfn|Pettofrezzo|Byrkit|1970|pp=23–24}}{{sfn|Long|1972|p=16}} Every positive integer is composite, ], or the ]&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}} E.g., 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 because each can only be divided by one and itself.
The first 15 composite numbers {{OEIS|id=A002808}} are
:4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, and 25.


The composite numbers up to 150 are:
==Properties==
: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 2 or more (not necessarily distinct) primes (]).
* Also, <math>(n-1)! \,\,\, \equiv \,\, 0 \pmod{n}</math> for all composite numbers ''n'' > 5. See also ].


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 ] can be written as 13 × 23, and the composite number ] can be written as 2<sup>3</sup> × 3<sup>2</sup> × 5; furthermore, this representation is unique ] the order of the factors. This fact is called the ].{{sfn|Fraleigh|1976|p=270}}{{sfn|Long|1972|p=44}}{{sfn|McCoy|1968|p=85}}{{sfn|Pettofrezzo|Byrkit|1970|p=53}}
==Kinds of composite numbers==

There are several known ]s that can determine whether a number is prime or composite which do not necessarily reveal the ] 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 ] 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 ]. 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 One way to classify composite numbers is by counting the number of prime factors. A composite number with two prime factors is a ] 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 ]. 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 ] and ''x'' is half the total of prime factors), while for the former
:<math>\mu(n) = (-1)^{2n} = 1\,</math>


:<math>\mu(n) = (-1)^{2x + 1} = -1.</math>
(where μ is the ] and ''x'' is half the total of prime factors), while for the former


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) = (-1)^{2n + 1} = -1.\,</math>


:<math>\mu(n) = 0</math>.{{sfn|Long|1972|p=159}}
Note however that for prime numbers the function also returns -1, and that <math>\mu(1) = 1</math>. For a number ''n'' with one or more repeated prime factors, <math>\mu(n) = 0</math>.


If ''all'' the prime factors of a number are repeated it is called a ]. If ''none'' of its prime factors are repeated, it is called ]. (All prime numbers and 1 are squarefree.) If ''all'' the prime factors of a number are repeated it is called a ] (All ]s are powerful numbers). If ''none'' of its prime factors are repeated, it is called ]. (All prime numbers and 1 are squarefree.)


For example, ] = 2<sup>3</sup> × 3<sup>2</sup>, all the prime factors are repeated, so 72 is a powerful number. ] = 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 ] (though the first two such numbers are 1 and 2). 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 ] (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 ]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 ]s and ]s, respectively.

==See also==
{{portal|Mathematics}}
* ]
* ]
* ]
* ]

==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 = ] | location = Reading }}
* {{ citation | first1 = I. N. | last1 = Herstein | author-link=Israel Nathan Herstein | year = 1964 | isbn = 978-1114541016 | title = Topics In Algebra | publisher = ] | location = Waltham }}
* {{ citation | first1 = Calvin T. | last1 = Long | year = 1972 | title = Elementary Introduction to Number Theory | edition = 2nd | publisher = ] | location = Lexington | lccn = 77-171950 }}
* {{ citation | first1 = Neal H. | last1 = McCoy | year = 1968 | title = Introduction To Modern Algebra, Revised Edition | publisher = ] | location = Boston | lccn = 68-15225 }}
* {{ citation | first1 = Anthony J. | last1 = Pettofrezzo | first2 = Donald R. | last2 = Byrkit | year = 1970 | title = Elements of Number Theory | publisher = ] | location = Englewood Cliffs | lccn = 77-81766 }}


== External links == == External links ==
*
* *
*


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


]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]
]

Latest revision as of 07:21, 14 December 2024

Integer having a non-trivial divisor
Demonstration, with Cuisenaire rods, of the divisors of the composite number 10
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
Composite numbers 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. Accordingly it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, or the unit 1, so the composite numbers are exactly the numbers that are not prime and not a unit. E.g., the integer 14 is a composite number because it is the product of the two smaller integers 2 × 7 but the integers 2 and 3 are not because each 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. (sequence A002808 in the OEIS)

Every composite number can be written as the product of two or more (not necessarily distinct) primes. For example, the composite number 299 can be written as 13 × 23, and the composite number 360 can be written as 2 × 3 × 5; furthermore, this representation is unique up to the order of the factors. This fact is called the fundamental theorem of arithmetic.

There are several known primality tests that can determine whether a number is prime or composite which do not necessarily reveal 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

μ ( 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} .

If 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 = 2 × 3, 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.

Euler diagram of numbers under 100:    Abundant    Primitive abundant    Highly abundant    Superabundant and highly composite    Colossally abundant and superior highly composite    Weird    Perfect    Composite    Deficient

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

Notes

  1. Pettofrezzo & Byrkit 1970, pp. 23–24.
  2. ^ Long 1972, p. 16.
  3. Fraleigh 1976, pp. 198, 266.
  4. Herstein 1964, p. 106.
  5. Fraleigh 1976, p. 270.
  6. Long 1972, p. 44.
  7. McCoy 1968, p. 85.
  8. Pettofrezzo & Byrkit 1970, p. 53.
  9. Long 1972, p. 159.

References

External links

Classes of natural numbers
Powers and related numbers
Of the form a × 2 ± 1
Other polynomial numbers
Recursively defined numbers
Possessing a specific set of other numbers
Expressible via specific sums
Figurate numbers
2-dimensional
centered
non-centered
3-dimensional
centered
non-centered
pyramidal
4-dimensional
non-centered
Combinatorial numbers
Primes
Pseudoprimes
Arithmetic functions and dynamics
Divisor functions
Prime omega functions
Euler's totient function
Aliquot sequences
Primorial
Other prime factor or divisor related numbers
Numeral system-dependent numbers
Arithmetic functions
and dynamics
Digit sum
Digit product
Coding-related
Other
P-adic numbers-related
Digit-composition related
Digit-permutation related
Divisor-related
Other
Binary numbers
Generated via a sieve
Sorting related
Natural language related
Graphemics related
Divisibility-based sets of integers
Overview Divisibility of 60
Factorization forms
Constrained divisor sums
With many divisors
Aliquot sequence-related
Base-dependent
Other sets
Categories: