Problem 5.29 The following Lemma is true, but the proof given for it below is invalid....

Transcribed Image Text:

Problem 5.29 The following Lemma is true, but the proof given for it below is invalid. Lemma. For any prime p and positive integers n, x1,x2,...,xn, if p | x1x2xn, then p|x; for some 1 ≤ i ≤n. = ak.) (Recall that a | b means that there exists an integer k such that b = False Proof. Proof by strong induction on n. The induction hypothesis P(n) is that the Lemma for n. Base case n = 1: When n = 1, we have p | x₁, therefore we can let i = 1 and conclude p | x₁. Induction step: Now assuming the claim holds for all k≤n, we must prove it for n + 1. Suppose p|x1x2*Xn+1. Let Yn = XnXn+1, SO X1X2•••Xn+1 = x1x2xn-1Yn. Since the right-hand side of this equation is a product of n terms, we have by induction that p divides one of them. If p xi for some i <n, then we have the desired i. Otherwise, pyn. But since yn is a product of the two terms xn, xn+1, we have by strong induction that p divides one of them. So, in this case, p|x; for i=nor i = n + 1. Identify exactly where the proof first makes an unjustified step and explain why it is unjustified. Problem 5.29 The following Lemma is true, but the proof given for it below is invalid. Lemma. For any prime p and positive integers n, x1,x2,...,xn, if p | x1x2xn, then p|x; for some 1 ≤ i ≤n. = ak.) (Recall that a | b means that there exists an integer k such that b = False Proof. Proof by strong induction on n. The induction hypothesis P(n) is that the Lemma for n. Base case n = 1: When n = 1, we have p | x₁, therefore we can let i = 1 and conclude p | x₁. Induction step: Now assuming the claim holds for all k≤n, we must prove it for n + 1. Suppose p|x1x2*Xn+1. Let Yn = XnXn+1, SO X1X2•••Xn+1 = x1x2xn-1Yn. Since the right-hand side of this equation is a product of n terms, we have by induction that p divides one of them. If p xi for some i <n, then we have the desired i. Otherwise, pyn. But since yn is a product of the two terms xn, xn+1, we have by strong induction that p divides one of them. So, in this case, p|x; for i=nor i = n + 1. Identify exactly where the proof first makes an unjustified step and explain why it is unjustified.

Answer rating: 100% (QA)

We use the principal of induction The result is plainly true when n 1 but for reason a... View the full answer