Citizendia

In number theory, the fundamental theorem of arithmetic (or unique-prime-factorization theorem) states that every natural number greater than 1 can be written as a unique product of prime numbers. Number theory is the branch of Pure mathematics concerned with the properties of Numbers in general and Integers in particular as well as the wider classes In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1 For instance,

6936 = 2^3 \times 3 \times 17^2 , \,\!
1200 = 2^4 \times 3 \times 5^2 . \,\!

There are no other possible factorizations of 6936 or 1200 into prime numbers. In Mathematics, factorization ( also factorisation in British English) or factoring is the decomposition of an object (for The above representation collapses repeated prime factors into powers for easier identification. Because multiplication is commutative and associative, the order of factors is irrelevant and usually written from least to greatest. In Mathematics, commutativity is the ability to change the order of something without changing the end result In Mathematics, associativity is a property that a Binary operation can have

Many authors take the natural numbers to begin with 0, which has no prime factorization. Thus Theorem 1 of Hardy & Wright (1979) takes the form, “Every positive integer, except 1, is a product of primes”, and Theorem 2 (their "Fundamental") asserts uniqueness. The number 1 is not itself prime, but since it is the product of no numbers, it is often convenient to include it in the theorem by the empty product rule. In Mathematics, an empty product, or nullary product, is the result of multiplying no numbers (See, for example, Calculating the gcd. In Mathematics, the greatest common divisor (gcd, sometimes known as the greatest common factor (gcf or highest common factor (hcf, of two non-zero )

Hardy & Wright define an abnormal number to be a hypothetical number that does not have a unique prime factorization. They prove the fundamental theorem of arithmetic by proving that there does not exist an abnormal number.

Contents

Applications

The fundamental theorem of arithmetic establishes the importance of prime numbers. Prime numbers are the basic building blocks of any positive integer, in the sense that each positive integer can be constructed from the product of primes with one unique construction. Finding the prime factorization of an integer allows derivation of all its divisors, both prime and non-prime.

For example, the above factorization of 6936 shows that any positive divisor of 6936 must have the form 2a * 3b * 17c, where a takes one of the 4 values in {0, 1, 2, 3}, where b takes one of the 2 values in {0, 1}, and where c takes one of the 3 values in {0, 1, 2}. Multiplying the numbers of independent options together produces a total of 4 * 2 * 3 = 24 positive divisors.

Once the prime factorizations of two numbers are known, their greatest common divisor and least common multiple can be found quickly. In Mathematics, the greatest common divisor (gcd, sometimes known as the greatest common factor (gcf or highest common factor (hcf, of two non-zero In Arithmetic and Number theory, the least common multiple or lowest common multiple ( lcm) or smallest common multiple of two For instance, from the above it is shown that the greatest common divisor of 6936 and 1200 is 23 * 3 = 24. However, if the prime factorizations are not known, the use of the Euclidean algorithm generally requires much less calculation than factoring the two numbers. In Number theory, the Euclidean algorithm (also called Euclid's algorithm) is an Algorithm to determine the Greatest common divisor (GCD

The fundamental theorem ensures that additive and multiplicative arithmetic functions are completely determined by their values on the powers of prime numbers. Different definitions exist depending on the specific field of application Outside number theory the term multiplicative function is usually used for Completely multiplicative functions This article discusses number theoretic multiplicative In Number theory an arithmetic function or arithmetical function is a Function defined on the set of Natural numbers (i

Proof

The theorem was practically proved by Euclid, but the first full and correct proof is found in the Disquisitiones Arithmeticae by Carl Friedrich Gauss. Euclid ( Greek:.) fl 300 BC also known as Euclid of Alexandria, is often referred to as the Father of Geometry The Disquisitiones Arithmeticae is a textbook of Number theory written by German Mathematician Carl Friedrich Gauss in 1798 Johann Carl Friedrich Gauss (ˈɡaʊs, Gauß Carolus Fridericus Gauss ( 30 April 1777 – 23 February 1855) was a German It may be important to note that Egyptians like Ahmes used earlier practical aspects of the factoring, and lowest common multiple, of the fundamental theorem of arithmetic allowing a long tradition to develop, as formalized by Euclid, and rigorously proven by Gauss. Ahmes (c 1680 BC-c 1620 BC (more accurately Ahmose) was an Egyptian scribe who lived during the Second Intermediate Period. In Arithmetic and Number theory, the least common multiple or lowest common multiple ( lcm) or smallest common multiple of two

Although at first sight the theorem seems 'obvious', it does not hold in more general number systems, including many rings of algebraic integers. This article deals with the ring of complex numbers integral over Z. This was first pointed out by Ernst Kummer in 1843, in his work on Fermat's last theorem. Ernst Eduard Kummer ( 29 January 1810 - 14 May 1893) was a German Mathematician. Fermat's Last Theorem is the name of the statement in Number theory that It is impossible to separate any power higher than the second into two like The recognition of this failure is one of the earliest developments in algebraic number theory. In Mathematics, algebraic number theory is a major branch of Number theory which studies the Algebraic structures related to Algebraic integers

Euclid's proof

The proof consists of two steps. In the first step every number is shown to be a product of zero or more primes. In the second, the proof shows that any two representations may be unified into a single representation.

Non-prime composite numbers

Suppose there were a positive integer which cannot be written as a product of primes. Then there must be a smallest such number (see well-order): let it be n. In Mathematics, a well-order relation (or well-ordering) on a set S is a Total order on S with the property that every This number n cannot be 1, because of the empty-product convention above. It cannot be a prime number either, since any prime number is a product of a single prime, itself. So it must be a composite number. Thus

n = ab

where both a and b are positive integers smaller than n. Since n is the smallest number which cannot be written as a product of primes, both a and b can be written as products of primes. But then

n = ab

can be written as a product of primes as well, a proof by contradiction. In Classical logic, a contradiction consists of a logical incompatibility between two or more Propositions It occurs when the propositions taken together yield This is a minimal counterexample argument. In Mathematics, the method of considering a minimal counterexample (or minimal criminal) combines the ideas of Inductive proof and Proof

Proof by infinite descent

A proof of the uniqueness of the prime factorization of a given integer uses infinite descent: Assume that a certain integer can be written as (at least) two different products of prime numbers: then there must exist a smallest integer s\! with such a property. In Mathematics, a proof by infinite descent is a particular kind of proof by Mathematical induction. In Mathematics, a product is the Result of multiplying, or an expression that identifies factors to be multiplied Denote these two factorizations of s\! as p_1\ldots p_m\! and q_1\ldots q_n\!, such that s = p_1 p_2\ldots p_m = q_1 q_2\ldots q_n\!.

No p_i\! (with 1 \le i \le m\!) can be equal to any q_j\! (with 1 \le j \le n\!), as there would otherwise be a smaller integer factorizable in two ways (by removing prime factors common in both products), violating the above assumption. Now it can be assumed without loss of generality that p_1\! is a prime factor smaller than any q_j\! (with 1 \le j \le n\!). Without loss of generality (abbreviated to WLOG or WOLOG and less commonly stated as without any loss of generality) is a frequently used expression Let d\! be the quotient and r\! the remainder from dividing q_1\! by p_1\!. In Mathematics, a quotient is the result of a division. For example when dividing 6 by 3 the quotient is 2 while 6 is called the dividend, and 3 the In Arithmetic, when the result of the division of two Integers cannot be expressed with an integer Quotient, the remainder is the amount "left By the division algorithm d\! and r\! are guaranteed to be integers such that q_1\ = dp_1 + r\! and 0 \le r < p_1\!. The division algorithm is a Theorem in Mathematics which precisely expresses the outcome of the usual process of division of Integers The name Note that r\! can't be 0\!, as that would make q_1\! a multiple of p_1\! and not prime. Also d \ge 1\!, since q_1\! is greater than p_1\!.

Substituting in for q_1\! in the original definition of s\! above,

s = p_1 p_2\ldots p_m = (dp_1 + r) q_2\ldots q_n\!

By distributivity:

s = p_1 p_2\ldots p_m = d p_1 q_2\ldots q_n + r q_2\ldots q_n\!

Define a new integer k = s - d p_1 q_2\ldots q_n = r q_2\ldots q_n\!. In Mathematics, and in particular in Abstract algebra, distributivity is a property of Binary operations that generalises the distributive law Since d \ge 1\!, it is clear that k\! must be smaller than s\!. And since r > 0\!, k\! must be positive. From the definition of k\!, it follows that:

k = p_1 p_2\ldots p_m - d p_1 q_2\ldots q_n\!

and by factoring out p_1\!:

k = p_1 (p_2\ldots p_m - d q_2\ldots q_n)\!

Therefore there is a prime factorization of k\! that includes p_1\!. But it is also true that

k = r q_2\ldots q_n\!

Since r < p_1\!, p_1\! cannot be a prime factor of r\!. Thus, by combining the prime factors of r\! with q_2\ldots q_n\!, it is also possible to construct a prime factorization of k\! that does not include p_1\!. Therefore k\! has two different prime factorizations, contradicting the original assumption that s\! is the smallest integer factorizable in more than one way. In Classical logic, a contradiction consists of a logical incompatibility between two or more Propositions It occurs when the propositions taken together yield Thus the original assumption must be false.

See also

References

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic