Proof of fundamental theorem of arithmetic

In summary, The conversation discusses a proof by induction for a specific way of expressing the product of primes. The goal is to prove that for all natural numbers except 0 and 1, there is only one way to write the prime factors. The two attachments from the textbook "Alan F Beardon, Algebra and Geometry" are referenced and the properties of set A, which contains all natural numbers except 0 and 1 with unique prime factorizations, are discussed. The conversation also addresses two cases, p1=q1 and p1<q1, and provides an equation for the latter case. The induction hypothesis is used in the proof, which assumes that if it can be shown that for n there is only one way to write the prime
  • #1
PcumP_Ravenclaw
106
4
Dear all,
Please help me understand the proof by induction for only one way of expressing the product of primes up to the order of the factors.

Please see the two attachments from the textbook "alan F beardon, algebra and geometry"

A is a set of all natural numbers excluding 1 and 0??

r and s in p1...pr = q1...qs can be same or two different numbers?

2 <= p1 <= ... <= pr means that the magnitude of p is progessively increasing from p1 to pr?

same condition 2 <= q1 <= ... <= qs for q1 also?

Two cases to consider (1) p1 = q1 (2) p1 < q1

in case (1) how is it possible to say that when p2...pr = q2...qs = m and 2 <= m <= n. "This means that the two factorizations of m are the same(up to order)" I thought this is what we are trying to prove! but here it is assumed even though there are a few prime factors involved from p2 to pr and q2 to qs and although the final product is m the prime factors may be different right which is our hypothesis??

in case (2) if p1 < q1 all other p terms should be greater than or equal to their corresponding q terms (i.e. p2 >= q2, etc.) only then will the equation

p1...pr = q1...qs

will hold and we can say that there is only one way to write a number as a product of primes disregarding the order of the factors

so in trying to make the two sides equal for the case p1 < q1 the following equation is obtained?

p1(p2...pr - q2...qs) = q2...qs(q1 - p1)

can you please derive this equation for the case p1 < q1 from the previous equation??

i understand that the q terms are less than n+1 because q1 is less because q1 = ( q1 - p1)

why should p1 be a prime factor of q1 - p1??

I cannot understand beyond this point!

Thanks in advance...
 

Attachments

  • photo1 (1).jpg
    photo1 (1).jpg
    66.3 KB · Views: 511
  • photo2.jpg
    photo2.jpg
    67.1 KB · Views: 568
Physics news on Phys.org
  • #2
Jose_Peeterson said:
A is a set of all natural numbers excluding 1 and 0??
A is the set of all natural numbers, not containing 0 and 1, which have unique prime factorizations. The goal is to prove with induction that A is all natural numbers except 0 and 1. Thus in the induction proof, the induction hypothesis is that all natural numbers (not equal to 0 or 1) less than or equal to n belong to A.

r and s in p1...pr = q1...qs can be same or two different numbers?
Both can occur.
2 <= p1 <= ... <= pr means that the magnitude of p is progessively increasing from p1 to pr?

same condition 2 <= q1 <= ... <= qs for q1 also?
Yes and yes.

Two cases to consider (1) p1 = q1 (2) p1 < q1

in case (1) how is it possible to say that when p2...pr = q2...qs = m and 2 <= m <= n. "This means that the two factorizations of m are the same(up to order)" I thought this is what we are trying to prove!
This is assumed. It is the induction hypothesis.

in case (2) if p1 < q1 all other p terms should be greater than or equal to their corresponding q terms (i.e. p2 >= q2, etc.) only then will the equation

p1...pr = q1...qs

will hold

If r=s then some pi must be greater qi, yes, but that is of no importance for the proof.

p1(p2...pr - q2...qs) = q2...qs(q1 - p1)
Hint: expand the parentheses at both sides, and use p1...pr = q1...qs.

why should p1 be a prime factor of q1 - p1??
Otherwise p1 must be a factor of some of q2, q3, ... ,qs, by the property that if a prime is a factor of a product of integers, it must be a factor of (at least) one of these integers.
 
Last edited:
  • #3
Dear Erland, Thanks for your reply...

Two cases to consider (1) p1 = q1 (2) p1 < q1
in case (1) how is it possible to say that when p2...pr = q2...qs = m and 2 <= m <= n. "This means that the two factorizations of m are the same(up to order)" I thought this is what we are trying to prove!This is assumed. It is the induction hypothesis.

What is the induction hypothesis here?? Is it, if it can be proved that for n there is only one way to write the prime factors for A ={2,3,4,5,6,7...n} then for n+1 also there is only one way to write the prime factors...

They have not shown the proof of the inductive step which is 'if n is true then n+1 is also true' so that it is true for all elements in A. Can you please show the anchor step and inductive step for this proof?

Expanding the parentheses

p1(p2...pr - q2...qs) = q2...qs(q1 - p1)

Hint: expand the parentheses at both sides, and use p1...pr = q1...qs.

p1p2...pr - p1q2q3...qs = q1q2...qs - p1q2...qs
so now?

but how can you explicitly show that p1 has decreased by q1 - p1 or q1 increased by q1 - p1. can you please derive??
 
  • #4
Jose_Peeterson said:
Dear Erland, Thanks for your reply...

What is the induction hypothesis here?? Is it, if it can be proved that for n there is only one way to write the prime factors for A ={2,3,4,5,6,7...n} then for n+1 also there is only one way to write the prime factors...

They have not shown the proof of the inductive step which is 'if n is true then n+1 is also true' so that it is true for all elements in A.
An apparently (but not really) stronger version of induction is used here. The induction hypothesis can be expressed just as you wrote above

there is only one way to write the prime factors for A ={2,3,4,5,6,7...n}

and the objective is to prove that this implies that

for n+1 also there is only one way to write the prime factors

This is done:

If p1p2...pr=q1q2...qs=n+1 (this being prime factorizations) with p1=q1, then p2p3...pr=q2q3...qs=m, say. Then, m is an integer <= n with two prime factorizations, so by the induction hypothesis, these prime factorizations are the same, so p2, p3, ..., pr is the same sequence of numbers as q2, q3, ..., qs, and since also p1=q1, the two prime factorizations of n+1 are the same.

p1p2...pr - p1q2q3...qs = q1q2...qs - p1q2...qs
so now?
We assumed that p1p2...pr=q1q2...qs, so this equality holds. Hence so does the original equality, with unexpanded parentheses.

but how can you explicitly show that p1 has decreased by q1 - p1 or q1 increased by q1 - p1. can you please derive??
It is not clear to me what you mean, but anyway:

p1 is a factor of the left side of p1(p2...pr - q2...qs) = q2...qs(q1 - p1), hence also of the right side. Since p1 is a prime, it must be a factor of either some of q2, q3, ... qs, or of q1-p1. But q2, q3, ..., are primes, so none of them can be divisible with the smaller prime p1. So p1 divides q1-p1, hence it divides (q1-p1)+p1=q1, which is impossible by the same reason as just before. This is a contradiction. Hence the assummption that p1<q1 is false, so p1=q1.
 
  • Like
Likes PcumP_Ravenclaw
  • #5
Erland said:
Otherwise p1 must be a factor of some of q2, q3, ... ,qs, by the property that if a prime is a factor of a product of integers, it must be a factor of (at least) one of these integers.

On reflection, this property needs not be used, and the author of the attached files did not intend this.

Instead, notice that m = p1(p2p3...pr - q2q3...qs) = q2q3...qs(q1-p1) <= n, so the induction hypothesis can be applied to m, which means that m has a unique prime factorization. From the left side, we see that p1 is one its prime factors, and from the right side, we see that q2, q3 ..., qs all are, and that all other prime factors must be factors in q1-p1. Since p1 < qj for all j, this means that p1 is none of the qj, so p1, being a prime factor of m, must be a factor in q1-p1, that is q1-p1=k*p1 for some k. Thus, q1 = (k+1)*p1, sp p1 is a factor in q1, which is impossible.
This contradiction yields that p1=q1.
 

FAQ: Proof of fundamental theorem of arithmetic

1. What is the fundamental theorem of arithmetic?

The fundamental theorem of arithmetic states that every positive integer greater than 1 can be written as a unique product of prime numbers.

2. Why is the fundamental theorem of arithmetic important?

The fundamental theorem of arithmetic is important because it provides a fundamental basis for number theory and is essential in many mathematical proofs and applications.

3. How do you prove the fundamental theorem of arithmetic?

The proof of the fundamental theorem of arithmetic involves using mathematical induction and the fundamental property of prime numbers, which states that any number that divides a product of two numbers must divide at least one of the numbers.

4. What is an example of the fundamental theorem of arithmetic in action?

An example of the fundamental theorem of arithmetic is the number 12, which can be written as 2 x 2 x 3. This shows that 12 is a unique product of prime numbers and cannot be broken down into any other combination of primes.

5. Is there a generalization of the fundamental theorem of arithmetic?

Yes, there is a generalization of the fundamental theorem of arithmetic known as the unique factorization theorem, which states that every positive integer greater than 1 can be written as a unique product of prime numbers, including negative and complex numbers.

Similar threads

Replies
7
Views
1K
Replies
3
Views
1K
Replies
3
Views
1K
Replies
1
Views
3K
Replies
5
Views
2K
Replies
1
Views
1K
Replies
5
Views
2K
Back
Top