You wish to prove by strong mathematical induction that the uniqueness part of t

Question

You wish to prove by strong mathematical induction that the uniqueness part of the unique factorisation theorem is true. That is, you wish to prove that for all integers n > 1, n cannot have two distinct prime factorisations. Somehow, you prove the case n= 2 as a base. The proof continues to the (strong) induction part. Given an integer k >2, WHAT do you assume is true about k (the induction hypothesis)?

Explanation / Answer

suppose we have to prove this by principal of mathematical induction, in case of 2! there is 1 prime factorization in case of 3! there is 2 .prime factorization Every positive integer n > 1 can be expressed as a product of primes (with perhaps only one factor), that is n = p?1 1 p?2 2 . . . p?r r , where p1, p2, . . . , pn are distinct primes and ?1, ?2, . . . , ?n are positive integers. This factoring is unique apart from the order of the prime factors. Proof. Let us prove first that any number n > 1 can be decomposed into a product of primes. If n = 2, the decomposition is trivial and we have only one factor, i.e., 2 itself. Let us assume that for all positive integers, which are less than n, a decomposition exists. If n is a prime, then n = n is the decomposition required. If n is composite, then n = n1n2, where n > n1 > 1 and n > n2 > 1 and by the induction hypothesis there are prime decompositions n1 = p1 . . . pr and n2 = q1 . . . qs for n1 and n2. Then we may combine them n = n1n2 = p1 . . . prq1 . . . qs and get the decomposition for n and prove the first statement. To prove that the decomposition is unique, we shall assume the existence of an integer capable of two essentially different prime decompositions, and from this assumption derive a contradiction. This will show that the hypothesis that there exists an integer with two essentially different prime decompositions is untenable, and hence the prime decomposition of every integer is unique. We will use the Least-integer Principle. Suppose that there exists an integer with two essentially different prime decompositions, then there will be a smallest such integer n = p1p2 . . . pr = q1q2 . . . qs, (1) where pi and qj are primes. By rearranging the order of the p

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.