Argument by Contradiction. There are infinitely many prime numbers.

Argument by Contradiction

The method of argument by contradiction proves a statement in the following way: First, the statement is assumed to be false. Then, a sequence of logical deductions yields a conclusion that contradicts either the hypothesis (indirect method ), or a fact known to be true (reductio ad absurdum).

This contradiction implies that the original statement must be true. This is a method that Euclid loved, and you can find it applied in some of the most beautiful proofs from his Elements. Euclid’s most famous proof is that of the infinitude of prime numbers.

Euclid’s theorem. There are infinitely many prime numbers.

Proof. Assume, to the contrary, that only finitely many prime numbers exist. List them as p1 = 2, p2 = 3, p3 = 5, . . . , pn. The number N = p1p2 · · · pn + 1 is divisible by a prime p, yet is coprime to p1, p2, . . . , pn. Therefore, p does not belong to our list of all prime numbers, a contradiction. Hence the initial assumption was false, proving that there are infinitely many primes.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: