Question Appendix.6: Using Proof by Contradiction A positive integer greater than...

Elementary Linear Algebra

Using Proof by Contradiction

A positive integer greater than 1 is a prime when its only positive factors are 1 and itself. Prove that there are infinitely many prime numbers.

The blue check mark means that this solution has been answered and checked by an expert. This guarantees that the final answer is accurate.
Learn more on how we answer questions.

Assume there are only finitely many prime numbers, $p_1, p_2, \cdot \cdot \cdot , p_n$ . Consider the number $N = p_1p_2 \cdot \cdot \cdot p_n + 1$ . This number is either prime or composite. If it is composite, then it can be factored as a product of primes. But, none of the primes $(p_1, p_2, \cdot \cdot \cdot , p_n)$ divide evenly into N. So, N is itself prime, and you have found a new prime number, which contradicts the assumption that there are only n prime numbers.

It follows that there are infinitely many prime numbers.

Related Answered Questions

Question: Appendix.2

Using Mathematical Induction Use mathematical induction to prove the following formula. Sn = 1 + 3 + 5 + 7 + ··· + (2n – 1) = n² ...

Verified Answer:

Mathematical induction consists of two distinct pa...

Question: Appendix.4

Using Mathematical Induction in Linear Algebra If A1, A2, · · ·, An are invertible matrices, then prove the generalization of Theorem 2.9. (A1 A2 A3 · · · An)^-1 = An^-1 · · · A3^-1A2^-1A1^-1 ...

Verified Answer:

1. The formula is valid trivially when n = 1 beca...

Question: Appendix.3

Using Mathematical Induction Use mathematical induction to prove the formula for the sum of the first n squares. Sn = 1² + 2² + 3² + 4² + · · · + n² = n(n + 1)(2n + 1) / 6 ...

Verified Answer:

1. When n = 1, the formula is valid, because [lat...

Question: Appendix.5

Using Proof by Contradiction Prove that √2 is an irrational number. ...

Verified Answer:

Begin by assuming that

\sqrt{2}

is...

Question: Appendix.1

Sum of Odd Integers Use the pattern to propose a formula for the sum of the first n odd integers. 1 = 1 1 + 3 = 4 1 + 3 + 5 = 9 1 + 3+ 5 + 7 = 16 1 + 3 + 5 + 7 + 9 = 25 ...

Verified Answer:

Notice that the sums on the right are equal to the...

Question: Appendix.7

Using Proof by Contradiction in Linear Algebra Let A and B be n × n matrices such that AB is singular. Prove that either A or B is singular. ...

Verified Answer:

Assume that neither A or B is singular. Because yo...

Question: Appendix.8

Using a Counterexample Use a counterexample to show that the statement is false. Every odd number is prime. ...

Verified Answer:

Certainly, you can list many odd numbers that are ...

Question: Appendix.9

Using a Counterexample in Linear Algebra Use a counterexample to show that the statement is false. If A and B are square singular matrices of order n, then A + B is a singular matrix of order n. ...

Verified Answer:

Let

A = \begin{bmatrix} 1 & 0 \\ 0 &...

Question: Appendix.10

Using a Counterexample in Linear Algebra Use a counterexample to show that the statement is false. The set of all 2 × 2 matrices of the form [1 b c d] with the standard operations is a vector space. ...

Verified Answer:

To show that the set of matrices of the given form...