Teorema fundamental da aritmética

Fundamental theorem of arithmetic Not to be confused with Fundamental theorem of algebra. In Disquisitiones Arithmeticae (1801) Gauss proved the unique factorization theorem [1] and used it to prove the law of quadratic reciprocity.[2] Na matemática, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors.[3][4][5] Por exemplo, {displaystyle 1200=2^{4}cdot 3^{1}cdot 5^{2}=(2cdot 2cdot 2cdot 2)cdot 3cdot (5cdot 5)=5cdot 2cdot 5cdot 2cdot 3cdot 2cdot 2=ldots } The theorem says two things about this example: primeiro, este 1200 can be represented as a product of primes, e em segundo lugar, that no matter how this is done, there will always be exactly four 2s, one 3, two 5s, and no other primes in the product.

The requirement that the factors be prime is necessary: factorizations containing composite numbers may not be unique (por exemplo, {displaystyle 12=2cdot 6=3cdot 4} ).

This theorem is one of the main reasons why 1 is not considered a prime number: E se 1 were prime, then factorization into primes would not be unique; por exemplo, {displaystyle 2=2cdot 1=2cdot 1cdot 1=ldots } This theorem generalizes to other algebraic structures, in particular to polynomial rings over a field. These structures are called unique factorization domains.

Conteúdo 1 Euclid's original version 2 Formulários 2.1 Canonical representation of a positive integer 2.2 Arithmetic operations 2.3 Arithmetic functions 3 Prova 3.1 Existência 3.2 Singularidade 3.3 Uniqueness without Euclid's lemma 4 Generalizações 5 Veja também 6 Notas 7 Referências 8 External links Euclid's original version Book VII, propositions 30, 31 e 32, and Book IX, proposição 14 of Euclid's Elements are essentially the statement and proof of the fundamental theorem.

If two numbers by multiplying one another make some number, and any prime number measure the product, it will also measure one of the original numbers.

— Euclid, Elements Book VII, Proposição 30 (In modern terminology: if a prime p divides the product ab, then p divides either a or b or both.) Proposição 30 is referred to as Euclid's lemma, and it is the key in the proof of the fundamental theorem of arithmetic.

Any composite number is measured by some prime number.

— Euclid, Elements Book VII, Proposição 31 (In modern terminology: every integer greater than one is divided evenly by some prime number.) Proposição 31 is proved directly by infinite descent.

Any number either is prime or is measured by some prime number.

— Euclid, Elements Book VII, Proposição 32 Proposição 32 is derived from proposition 31, and proves that the decomposition is possible.

If a number be the least that is measured by prime numbers, it will not be measured by any other prime number except those originally measuring it.

— Euclid, Elements Book IX, Proposição 14 (In modern terminology: a least common multiple of several prime numbers is not a multiple of any other prime number.) Book IX, proposição 14 is derived from Book VII, proposição 30, and proves partially that the decomposition is unique – a point critically noted by André Weil.[6] De fato, in this proposition the exponents are all equal to one, so nothing is said for the general case.

Artigo 16 of Gauss' Disquisitiones Arithmeticae is an early modern statement and proof employing modular arithmetic.[1] Applications Canonical representation of a positive integer Every positive integer n > 1 can be represented in exactly one way as a product of prime powers: {displaystyle n=p_{1}^{n_{1}}p_{2}^{n_{2}}cdots p_{k}^{n_{k}}=prod_{i=1}^{k}p_{eu}^{n_{eu}}} where p1 < p2 < ... < pk are primes and the ni are positive integers. This representation is commonly extended to all positive integers, including 1, by the convention that the empty product is equal to 1 (the empty product corresponds to k = 0). This representation is called the canonical representation[7] of n, or the standard form[8][9] of n. For example, 999 = 33×37, 1000 = 23×53, 1001 = 7×11×13. Factors p0 = 1 may be inserted without changing the value of n (for example, 1000 = 23×30×53). In fact, any positive integer can be uniquely represented as an infinite product taken over all the positive prime numbers: {displaystyle n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}cdots =prod _{i=1}^{infty }p_{i}^{n_{i}},} where a finite number of the ni are positive integers, and the rest are zero. Allowing negative exponents provides a canonical form for positive rational numbers. Arithmetic operations The canonical representations of the product, greatest common divisor (GCD), and least common multiple (LCM) of two numbers a and b can be expressed simply in terms of the canonical representations of a and b themselves: {displaystyle {begin{alignedat}{2}acdot b&=2^{a_{1}+b_{1}}3^{a_{2}+b_{2}}5^{a_{3}+b_{3}}7^{a_{4}+b_{4}}cdots &&=prod p_{i}^{a_{i}+b_{i}},\gcd(a,b)&=2^{min(a_{1},b_{1})}3^{min(a_{2},b_{2})}5^{min(a_{3},b_{3})}7^{min(a_{4},b_{4})}cdots &&=prod p_{i}^{min(a_{i},b_{i})},\operatorname {lcm} (a,b)&=2^{max(a_{1},b_{1})}3^{max(a_{2},b_{2})}5^{max(a_{3},b_{3})}7^{max(a_{4},b_{4})}cdots &&=prod p_{i}^{max(a_{i},b_{i})}.end{alignedat}}} However, integer factorization, especially of large numbers, is much more difficult than computing products, GCDs, or LCMs. So these formulas have limited use in practice. Arithmetic functions Main article: Arithmetic function Many arithmetic functions are defined using the canonical representation. In particular, the values of additive and multiplicative functions are determined by their values on the powers of prime numbers. Proof The proof uses Euclid's lemma (Elements VII, 30): If a prime divides the product of two integers, then it must divide at least one of these integers. Existence It must be shown that every integer greater than 1 is either prime or a product of primes. First, 2 is prime. Then, by strong induction, assume this is true for all numbers greater than 1 and less than n. If n is prime, there is nothing more to prove. Otherwise, there are integers a and b, where n = a b, and 1 < a ≤ b < n. By the induction hypothesis, a = p1 p2 ⋅⋅⋅ pj and b = q1 q2 ⋅⋅⋅ qk are products of primes. But then n = a b = p1 p2 ⋅⋅⋅ pj q1 q2 ⋅⋅⋅ qk is a product of primes. Uniqueness Suppose, to the contrary, there is an integer that has two distinct prime factorizations. Let n be the least such integer and write n = p1 p2 ... pj = q1 q2 ... qk, where each pi and qi is prime. We see that p1 divides q1 q2 ... qk, so p1 divides some qi by Euclid's lemma. Without loss of generality, say p1 divides q1. Since p1 and q1 are both prime, it follows that p1 = q1. Returning to our factorizations of n, we may cancel these two factors to conclude that p2 ... pj = q2 ... qk. We now have two distinct prime factorizations of some integer strictly smaller than n, which contradicts the minimality of n. Uniqueness without Euclid's lemma The fundamental theorem of arithmetic can also be proved without using Euclid's lemma.[10] The proof that follows is inspired by Euclid's original version of the Euclidean algorithm. Assume that {displaystyle s} is the smallest positive integer which is the product of prime numbers in two different ways. Incidentally, this implies that {displaystyle s} , if it exists, must be a composite number greater than {displaystyle 1} . Now, say {displaystyle {begin{aligned}s&=p_{1}p_{2}cdots p_{m}\&=q_{1}q_{2}cdots q_{n}.end{aligned}}} Every {displaystyle p_{i}} must be distinct from every {displaystyle q_{j}.} Otherwise, if say {displaystyle p_{i}=q_{j},} then there would exist some positive integer {displaystyle t=s/p_{i}=s/q_{j}} that is smaller than s and has two distinct prime factorizations. One may also suppose that {displaystyle p_{1}

Se você quiser conhecer outros artigos semelhantes a Teorema fundamental da aritmética você pode visitar a categoria fatoração.