We previously talked about Fundamental Theorem of Arithmetic which states that:
Any integer
has a unique factorization (up to order) 
,where 
are distinct primes and 
are positive integers. In this section, let’s look at the uniqueness of the factorization.MöBIUS FUNCTION >
UNIQUENESS OF FACTORIZATION
May want to check out:
FUNDAMENTAL THEOREM OF ARITHMETIC
MERTENS FUNCTION AND IT'S CONJECTURES
Similar to:
VIDEO LECTURE
MAIN CONCEPTS
We use the induction hypothesis for some  where  and later substitute  with  . to show that an integer  has a unqiue factorization. Get the Printer Friendly VersionCOMMENTS
Feel free to leave any comments on the lesson - your views, improvements, mistakes, clarification of concepts, or vote to have this lesson revised. |
CONCEPT
We will prove the uniqueness property by induction too. As with the previous proof, we need to divide the case when
 is prime and when  is not prime.
If
For our induction hypothesis, suppose the uniqueness property holds for some integer
be two factorizations of Suppose Suppose then
In case you are not familiar with the notation, the “x|y” means x divides y with no remainder. If Okay, let’s slow things down a bit. You might be lost in the last step. Here is another way of looking at it. Remember in our expression of We know that
We are almost done. Our last step was to simply show I hope I have done a decent job in showing the uniqueness property of the fundamental theorem of arithmetic. All information presentated, less questions and exercises, is original content of Donny, with slight references to various books.
Video courtesy of YouTube.com service. |
, then clearly 
has a unique factorization as a product of prime powers namely,
such that 
. Let
into a product of prime powers. Again, the labeling of the terms is necessary as we suppose the 
does have two distinct factorization anticipating that a contradiction will occur.
is prime. In that case, we must have 
and 
since the only positive divisors of 
are 1 and 
itself, implying 
. The factorization is unique.
is not a prime. Now 
and 
, the we also know 
, the other expression of 
and in turn 
for some i.
, we have factorized it into prime powers. For the purpose of this discussion I would like to call prime powers, ‘numbers in their purest form’ simply because they can’t be factored any further. So lets say we have 
where 
, and 
, are prime numbers and so 
can’t be factored any further. If there’s a prime number that divided 
, i.e., 
, there must be a factor of 
‘hidden in 
’, which can also be divided by 
. That is to say, 
or 
. We are thus finding that hidden factor 
which can be divided by 
.
for some i. By reordering the 
, we can assume that 
and so 
or 
and since 
and 
are primes, 
. Hence,
divides 
for both factorizations. We are just left in using our induction hypothesis. Now 
is an integer and 
. We have already proven the induction hypothesis to be true for 
. So we can now pick a value for 
, divide by 
which will make it less than 
, and by induction starting with 
, say that it has a unique factorization.
