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 editNext edit →Content deleted Content addedVisualWikitext
Revision as of 00:11, 13 May 2008 editPrimeHunter (talk | contribs)Administrators79,265 edits Undid revision 211980705 by 138.88.40.7 (talk). Too trivial external link, OEIS sequence already linked← Previous edit Revision as of 21:49, 13 May 2008 edit undoHayson1991 (talk | contribs)242 editsm →Kinds of composite numbersNext edit →
Line 13: Line 13:
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> :<math>\mu(n) = (-1)^{2n} = 1\,</math>


(where μ is the ] and ''x'' is half the total of prime factors), while for the former (where μ is the ] and ''x'' is half the total of prime factors), while for the former


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


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>. 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>.

Revision as of 21:49, 13 May 2008

Divisibility-based sets of integers
Overview Divisibility of 60
Factorization forms
Constrained divisor sums
With many divisors
Aliquot sequence-related
Base-dependent
Other sets

A composite number is a positive integer which has a positive divisor 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 one is either a prime number or a composite number. The number one is a unit - it is neither prime nor composite. For example, the integer 14 is a composite number because it can be factored as 2 × 7.

The first 15 composite numbers (sequence A002808 in the OEIS) are

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, and 25.

Properties

  • Every composite number can be written as the product of 2 or more (not necessarily distinct) primes (Fundamental theorem of arithmetic).
  • Also, ( n − 1 ) ! ≡ 0 ( mod n ) {\displaystyle (n-1)!\,\,\,\equiv \,\,0{\pmod {n}}} for all composite numbers n > 5. See also Wilson's theorem.

Kinds of composite numbers

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 n = 1 {\displaystyle \mu (n)=(-1)^{2n}=1\,}

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

μ ( n ) = ( − 1 ) 2 n + 1 = − 1. {\displaystyle \mu (n)=(-1)^{2n+1}=-1.\,}

Note however that for prime numbers the function also returns -1, and that μ ( 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. If none of its prime factors are repeated, it is called squarefree. (All prime numbers and 1 are 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).

External links

Categories: