User:Virginia-American/Sandbox

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 p₁ < p₂ < ... < p_k and positive integers a₁, a₂, ..., a_k, so that

$n=p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}.$ (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 $ω(n),$ and the number of prime factors counted with multiplicity is denoted by $Ω(n).$ Thus, for the n factored above, $ω(n) = k$ and $\Omega(n) = \sum_{j=1}^{k}a_j.$

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

Since a number m divides n if and only if $m=p_1^{b_1}p_2^{b_2} \cdots p_k^{b_k}$ where 0 ≤ b_i ≤ a_i for all i, 1 ≤ i ≤ k,

$d(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)\;\;$ and

$\begin{align} \sigma(n) &= (1+p_1+p_1^2+\cdots+p_1^{a_1})\times\cdots\times(1+p_k+p_k^2+\cdots+p_k^{a_k}) \\ & = \frac{p_1^{a_1+1}-1}{p_1-1}\times\frac{p_2^{a_2+1}-1}{p_2-1}\times\cdots\times\frac{p_k^{a_k+1}-1}{p_k-1} \\ \end{align}$

For example 12 = 2²×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.

[edit] Detecting composite numbers

Main article: primality test

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 a^p–1 ≡ 1 (mod p). Therefore, if for some a, a^{n – 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 $F_{14}=2^{2^{14}}+1$ the 14th Fermat number.^[2]

[edit] Kinds of composite numbers

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

[edit] Statistics

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 = 2⁴ × 3 × 5² would certainly be called round. the roundness of a number like 2187 = 3⁷ 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 10⁷ is a little less than 3, and loglog 10⁸⁰ 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

$\mu(n) = (-1)^{2x} = 1\,$

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

$\mu(n) = (-1)^{2x + 1} = -1.\,$

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

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

[edit] See also

[edit] Notes

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

[edit] References

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

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

Bach, Eric & Shallit, Jeffrey (1966), Algorithmic Number Theory (Vol I: Efficient Algorithms), Cambridge: The MIT Press, ISBN 0-262-02045-5

Cohen, Henri (1993), A Course in Computational Algebraic Number Theory, Berlin: Springer, ISBN 3-540-55640-0

Crandall, Richard & Pomeramce, Carl (2001), Prime Numbers: A Computatinal Perspective, New York: Springer, ISBN 0-387-04777-9

Davenport, Harold (2000). Multiplicative Number Theory (Third edition). New York: Springer. ISBN 0-387-95097-4.

Edwards, Harold (1977). Fermat's Last Theorem. New York: Springer. ISBN 0-387-90230-9.

Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A7.1: AN1, pg.249.}}

Hardy, G. H. & Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0198531715

Ireland, Kenneth & Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X

Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66967-4

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.

Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5

User:Virginia-American/Sandbox

From Wikipedia, the free encyclopedia

Contents

[edit] Arithmetic functions

[edit] Detecting composite numbers

[edit] Kinds of composite numbers

[edit] Statistics

[edit] See also

[edit] Notes

[edit] References

[edit] External links

Views

Navigation

Interaction

Search