(a) Find the error in the following proof. Claim: for all n element N, either n
ID: 3123209 • Letter: #
Question
(a) Find the error in the following proof. Claim: for all n element N, either n is prime, or n divides (n - 1)! "Proof": Suppose n isn't prime. Then by definition, n can be written as a production n = a times b of strictly smaller natural numbers. Since a, b are both less than n, they are both less then or equal to n - 1, and hence both a and b appear in the expansion (n - 1)! = (n - 1) times (n - 2) times (n - 3) times times 3 times 2 times 1 Therefore, n divides (n - 1)!. (b) Modify the approach above to prove the following true statement: for all n element N, either n is prime, or n is square, or n divides (n - 1)!.Explanation / Answer
(a) The 'proof' fails to take care of the case when a = b.
In the case of a=b, a (or b) appears only once. So a divided (n-1)! but not necessarily ab.
(b) Claim: For all n N, either n is a prime or n is a square or n divides (n-1)!
Proof: Suppose n isn't prime. Then by definition, n can be written as a product n = a*b of strictly smaller natural numbers. Since a,b are both less than n, they are both less than or equal to n-1, hence both a and be appear in the expansion
(n-1)! = (n-1) * (n-2) * (n-3) * ......* 3 * 2 * 1
unless a=b where the they appear only once. In that case n = a*a = a2 and so n is a square.
Therefore n divides (n-1)! or n is a square.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.