The fundamental theorem of arithmetic

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

The unique factoring theorem was tested by Gauss in his 1801 book, Disquisitions Arithmeticae. In it, Gauss used the fundamental theorem to test the quadratic reciprocity law.

In mathematics, and particularly in number theory, the fundamental theorem of arithmetic or unique factorization theorem states that every positive integer greater than 1 is a number prime or a unique product of prime numbers. For example,

{displaystyle 6936=2^{3}cdot 3cdot 17^{2}}

{displaystyle 1200=2^{4}cdot 3cdot 5^{2}}

There is no other factorization of 6936 and 1200 in terms of prime numbers. Since multiplication is commutative, the order of the factors is irrelevant; for this reason, the theorem is usually stated as a unique factorization except in the order of the factors.

Applications

Canonical representation of a positive integer

All positive integer n > 1 can be represented in exactly one way as a product of powers of prime numbers:

{displaystyle n=p_{1}^{alpha _{1}}p_{2}^{alpha _{2}}cdots p_{k}^{alpha _{k}}=prod _{i=1}^{k}p_{i}^{alpha _{i}}}

where p₁ < p₂ < … < p_k are prime and α_i are positive integers.

This representation is called the canonical representation of n, or standard form of n.

For example, 999 = 3³×37, 1000 = 2³×5³1001 = 7×11×13

Note that the factors p⁰ = 1 can be inserted without changing the value of n (eg, 1000 = 2 ³×3⁰×5³). Indeed, any positive number can only be represented as an infinite product taken over the entire set of prime numbers,

{displaystyle n=2^{alpha _{2}}3^{alpha _{3}}5^{alpha _{5}}7^{alpha _{7}}cdots =prod _{mathbb {P} }p^{alpha _{p}}}

where a finite number of α_p are positive integers, and the rest are zero. Allowing negative exponents provides a canonical form for the rational numbers.

Importance

The theorem states the importance of prime numbers. These are the "building blocks" out of which positive integers are "built," in the sense that every positive integer can be built as a product of prime numbers in only one way.

Knowing the factoring in cousins of a number allows you to find all your dividers, cousins or compounds. For example, the previously given factoring of 6936 shows that any positive divider 6936 must have the form: ${displaystyle 2^{a}cdot 3^{b}cdot {17}^{c}}$ , where 0 ≤ a ≤ 3 (4 possible values), 0 ≤ b ≤ 1 (2 possible values), and 0 ≤ c ≤ 2 (3 possible values). Multiplying the number of independent options you get a total of ${displaystyle 4cdot 2cdot 3=24}$ positive dividers

Once you know the prime factorization of two numbers, you can easily find their greatest common divisor and least common multiple. For example, from the above factorizations of 6936 and 1200 it can be deduced that their greatest common divisor is 2³ 3 = 24. However, if the prime factorization is not known, using Euclid's algorithm generally requires much less computation than factor the two numbers.

The Fundamental Theorem implies that additive and multiplicative arithmetic functions are completely determined by their values in powers of prime numbers.

Any integer n greater than 1 can be uniquely written, barring order, as a product of prime numbers.

Demo

The theorem was practically first proved by Euclid (it is Proposition 14 of book 9 of his Elements), although the first complete proof appeared in Carl Friedrich Gauss's Disquisitiones Arithmeticae.

Although at first sight the theorem seems "obvious", it does not hold in more general number systems, among these many rings of algebraic integers. Ernst Kummer was the first to notice this in 1843, in his work on Fermat's Last Theorem. The recognition of this flaw is one of the first advances in algebraic number theory.

Euclid's proof

The proof is done in two steps. In the first step, it is shown that every number is a product of prime numbers (including the empty product). In the second step, it is shown that both representations are equal.

Prime decomposition

Suppose there exists some positive integer that cannot be represented as a product of primes. So there must be a minimum number n with that property. This number n cannot be 1, by the above convention. Nor can it be a prime, because every prime is the product of a single prime number: itself.

Since it is not prime, by definition there is a number other than itself and other than 1 that divides it. Call that number a, by definition of divisibility there exists b such that n = ab.

So, n = ab, where a and b are positive integers less than n. Since n is the smallest positive integer for which the theorem fails, both a and b can be written as products of primes. But then n = ab can also be written as a product of primes, which is contradictory.

Uniqueness

The proof of uniqueness rests on the following fact: if a prime number p divides a product ab, then it divides a o divides b (Euclid's lemma). To prove this lemma, if p is assumed not to divide a, then p and a are primes between if and by Bézout's identity there exist x and y integers such that px + ay = 1. Multiplying by b yields pbx + aby = b, and since the two addends on the left are divisible by p, the term on the right is also divisible by p.

Given two products of primes that have the same result, take a prime p of the first product. It divides the first product, and therefore also the second. Due to the above fact, p must divide at least one factor of the second product; but the factors are all prime, so p must be equal to one of the factors of the second product. You can then cancel p of both products. Continuing in this way, all the factors of both products will be canceled, with which they must coincide exactly.

Proof by infinite descent

Another proof of the uniqueness of prime factorizations of a given integer uses the method of infinite descent.

Suppose a certain integer can be written as a product of prime factors in (at least) two different ways. So, there must exist a minimum integer s with that property. Let p₁·…·p_m and q₁…·q_n two different factorizations of s. No p_i (with 1 ≤ i ≤ m) can be equal to some q_j (with 1 ≤ j ≤ n), otherwise there would be a number less than s which could be factored in two ways (obtained by removing factors common to both products) contradicting the previous assumption. It can then be assumed without loss of generality that p₁ is a smaller prime factor than all q_j (with 1 ≤ j ≤ n). Consider in particular q₁. Then there exist integers d and r such that

{displaystyle {q_{1} over p_{1}}=d+{r over p_{1}}}

y 0 < r < p₁ < q₁ (r cannot be 0, since in such a case q₁ would be a multiple of p₁ and therefore composite). Multiplying both sides by s / q₁ gives

{displaystyle p_{2}ldots p_{m}=left(d+{r over p_{1}}right)q_{2}ldots q_{n}=dcdot q_{2}ldots q_{n}+{rcdot q_{2}ldots q_{n} over p_{1}}.}

The second term of the last expression must be equal to an integer (since the other terms are too), which will be called k; this is,

{displaystyle k={rcdot q_{2}ldots q_{n} over p_{1}},}

where it is obtained from,

{displaystyle p_{1}cdot k=rcdot q_{2}ldots q_{n}.}

The value of both sides of this equation is obviously less than s, but it is still large enough to be factorable. Since r is less than p₁, the two factorizations obtained on both sides after writing k and r as a product of primes must be different. This contradicts the assumption that s is the smallest integer that can be factored in more than one way. Therefore, the initial assumption must be false.

Proof by Abstract Algebra

Let n be an integer. Z_n is a finite group, so it has a composition series. By definition, the factors in a composition series are simple; therefore, in the series of Z_n these must be of the form Z_p for some prime p. Since the order of Z_n is the product of the orders of the factors in its composition series, this gives a factorization of n in prime numbers. But the Jordan-Hölder theorem states that a composition series is unique, and therefore the factorization of n must be unique.

Contenido relacionado

Más resultados...