请输入您要查询的字词:

 

单词 FundamentalTheoremOfArithmeticProofOfThe
释义

fundamental theorem of arithmetic, proof of the


To prove the fundamental theorem of arithmeticMathworldPlanetmath, we must show that eachpositive integer has a prime decomposition and that each suchdecomposition is unique up to the order (http://planetmath.org/OrderingRelation) of the factors. Beforeproceeding with the proof, we note that in any integral domainMathworldPlanetmath, everyprime is an irreducible elementMathworldPlanetmath. Furthermore, by Euclid’s lemma, every irreducible element in is prime. As a result, prime elementsMathworldPlanetmath and irreducible elements are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath in . We will use this fact to prove the theorem.

Note: all our arithmetic will be carried out in the natural numbersMathworldPlanetmath, not the integers.

Existence

Now we prove the existence of a prime decomposition. Since 1 has aprime decomposition and any prime has a prime decomposition, itsuffices to show that any composite numberMathworldPlanetmath has a prime decomposition.We claim that any composite number is divisible by some prime numberMathworldPlanetmath.To see this, assume n is a composite positive integer. Thenthere exist positive integers a and b, necessarily strictlysmaller than n, such that n = ab. If a is notprime we can write it as a productPlanetmathPlanetmath of smaller positive integers in thesame way. Continuing this process, we obtain a strictly decreasingsequenceMathworldPlanetmath of natural numbers. By the well-ordering principle, thissequence must terminate, and by construction, it must terminate in aprime number. Hence n is divisible by a prime number, asdesired.

To completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof of existence, we apply the well-orderingprinciple again. If n is composite, then it is divisible by someprime. Moreover, the quotient is strictly smaller than n. Ifthe quotient is not prime then as before we find a prime that dividesit; continuing this process, we produce a strictly decreasing sequenceof natural numbers. By the well-ordering principle, this sequenceterminates in a prime number. The product of the prime numbers wefound in the construction of this sequence is simply n. Thusevery composite number has a prime decomposition.

Uniqueness

Now we show uniqueness up to order of factors. Suppose we are giventwo prime decompositions

n=p1pk=q1q

of n, where k and the factors in each prime decompositionare arranged in nondecreasing order. Since p1 divides n, itdivides the product q1q, so by primality must dividesome qi. Thus there is a natural number b such that qi=bp1. Since qi is an irreducible element and p1 is not aunit, it must be that b is a unit, that is, b = 1. Hencep1=qiq1. Similarly, there is some j such that q1=pjp1. Since p1q1 and q1p1, it follows thatp1=q1. Cancelling these factors yields the simpler equation

p2pk=q2q.

By repeating the above procedure we can show that pi=qi for alli from 0 to k. Cancelling these factors gives the equation

1=qk+1q.

Since a nontrivial product of primes is greater than 1, the right-handside of this equation is the empty product. We conclude that k =l. Hence all prime decompositions of n use the same numberof factors, and the factors which appear are unique up to the order inwhich they appear. This completes the proof of uniqueness and therebythe proof of the theorem.

Remark. Note that Euclid’s Lemma is necessary in order to prove the uniqueness portion of the theorem. Also, an alternative way of proving the existence portion of the theorem is to use inductionMathworldPlanetmath: if n is composite, then n=ab for some integers a,b<n (this is true, for if one of a,b is n, then the other integer must be 1). By induction, both a and b can be written as product of primes, which implies that n is a product of primes.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/3 12:19:53