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.

Arithmetic functions

edit

The fundamental theorem of arithmetic says that every positive integer can be represented as the product of prime numbers and that (except for their order) this representation is unique: for any n > 0, there are prime numbers p1 < p2 < ... < pk and positive integers a1, a2, ..., ak, so that

  (The number 1 corresponds to the empty product).

Several arithmetic functions that are important in the study of composite numbers are defined using this factorization.

The number of distinct prime factors of n is denoted by   and the number of prime factors counted with multiplicity is denoted by   Thus, for the n factored above,   and  

The number of divisors (including 1 and n itself) of n is denoted by   and the sum of the divisors is denoted by  


Since a number m divides n if and only if   where 0 ≤ biai for all i, 1 ≤ ik,

  and

 

For example 12 = 22×3, so ω(12) = 2, Ω(12) = 3, d(12) = 6 and σ(12) = 28. (The divisors of 12 are 1, 2, 3, 4, 6, and 12.)

Therefore, n is composite is equivalent to each of the three statements Ω(n) > 1, d(n) > 2, and σ(n) > n + 1.

Detecting composite numbers

edit

The obvious way to prove that a number is composite is to find a nontrivial factor. This is only feasible for numbers less than about 200 decimal digits long. (See Integer factorization records.)

Any formula that is satisfied by prime numbers but is not necessarily true for composite numbers can be used to test for compositeness: if n does not satisfy the formula then n is composite. For example Fermat's theorem says that if p is prime and does not divide a then ap–1 ≡ 1 (mod p). Therefore, if for some a, an – 1 is not ≡ 1 (mod n), n is composite. This is practical because there are efficient algorithms for modular exponentiation. A similar test is based on Euler's criterion. See the articles on pseudoprimes and Carmichael numbers for examples of composite numbers that cannot be detected by these and similar tests.

Wilson's theorem says that (n – 1)! ≡ –1 (mod n) if and only if n is prime. This is not a practical way to determine whether a number is prime or composite because there is no known algorithm for efficiently calculating factorials (mod n).

By using tests of this sort, it has been determined that some numbers are composite even though no factor is known. An example[1] is   the 14th Fermat number.[2]

Kinds of composite numbers

edit

A number n such that Ω(n) = 2 (i.e. n is the square of a prime or the product of two distinct primes) is called a semiprime or a 2-almost prime. More generally, if Ω(n) = k, n is called a k-almost-prime. Several conjectures about prime numbers have been proved for 2-almost-primes. See twin prime conjecture, Goldbach's conjecture, and Chen's theorem.

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.) The radical or squarefree core of a number n (prime or composite) is the product of all the distinct primes dividing n. See ABC conjecture.

If none of the prime factors of n exceed B, n is called B-smooth. Smooth numbers are important in several integer factorization algorithms, including Pollard's p - 1 algorithm, the quadratic sieve and the number field sieve.

A composite number with three distinct prime factors is called a sphenic number.

A number n that has more divisors than any x < n is called a highly composite number (though the first two such numbers are 1 and 2).

Some authors[3] call numbers that have been proved composite without any factors being known "genuine composites".

Statistics

edit

Hardy and Wright wrote[4]

A number is usually called 'round' if it is the product of a considerable number of compararively small factors. Thus 1200 = 24 × 3 × 52 would certainly be called round. the roundness of a number like 2187 = 37 is obscured by the decimal notation.

It is a matter of common observation that round numbers are very rare.

They continue

Either of the functions ω(n) or Ω(n) gives a natural measure of the 'roundness' of n, and each of them is usually about loglog n, a function of n which increases very slowly. Thus loglog 107 is a little less than 3, and loglog 1080 is a little larger than 5.

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

 

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

 

Note however that for prime numbers the function also returns -1, and that  . For a number n with one or more repeated prime factors,  .


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

See also

edit


Notes

edit
  1. ^ as of March 2008
  2. ^ Crandall & Pomerance, p. 26
  3. ^ Crandall & Pomerance, p. 26
  4. ^ Hardy & Wright, § 22.12, pp.358–359


References

edit

The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.


  • Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0387962549 {{citation}}: |first2= has generic name (help)
  • Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8 {{citation}}: |first2= has generic name (help)


  • Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X
  • Manders, Kenneth L.; Adleman, Leonard (1978). "NP-Complete Decision Problems for Binary Quadratics". Journal of Computer and System Sciences. 16 (2): 168–184. doi:10.1016/0022-0000(78)90044-2.{{cite journal}}: CS1 maint: date and year (link)
  • Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5
edit