Proof by contradictionEdexcel International A Level Maths: Revision notes

To prove a statement $P$ by contradiction: (1) assume that $P$ is false, that is assume the negation of $P$; (2) argue logically from that assumption; (3) reach a result that is impossible, such as a number that is both even and odd, or a statement that contradicts the assumption or a known fact; (4) conclude that the assumption was wrong, so $P$ is true. Each step must follow from the one before. The contradiction is the whole point, so state it clearly, for example 'this contradicts the assumption that $p$ and $q$ have no common factor'. Negations: the negation of 'for all $n$, $n^2$ is even' is 'there exists an integer $n$ with $n^2$ odd'; the negation of 'there is no integer with...' is 'there is an integer with...'; the negation of 'irrational' is 'rational'.

Assume $\sqrt2=\frac{p}{q}$ where $p,q$ are integers with no common factor (the fraction is in its lowest terms) and $q\neq0$. Squaring, $2=\frac{p^2}{q^2}$, so $p^2=2q^2$. So $p^2$ is even, and therefore $p$ is even (the square of an odd number is odd). Write $p=2k$. Then $4k^2=2q^2$, so $q^2=2k^2$, so $q^2$ is even and $q$ is even. Now $p$ and $q$ are both even, so they share the factor 2. This contradicts the assumption that they have no common factor. Therefore $\sqrt2$ is irrational. The same argument shows that $\sqrt3$, $\sqrt5$ and $\sqrt p$ for any prime $p$ are irrational.

Assume there are only finitely many primes, $p_1,p_2,\ldots,p_n$. Let $N=p_1p_2\cdots p_n+1$. Dividing $N$ by any $p_i$ leaves remainder 1, so no $p_i$ divides $N$. But $N>1$ has at least one prime factor. That prime factor is not in the list. This contradicts the assumption that the list contains all the primes. So there are infinitely many primes. Note that $N$ need not itself be prime: with the primes up to 13, $N=30031=59\times509$, and the argument works because $59$ and $509$ are primes outside the list.

Many unfamiliar proofs rely on a few facts. An integer is either even or odd, never both. The square of an even number is even and of an odd number is odd. If a product of integers is even, at least one factor is even. If a number is a multiple of 7, so is any integer multiple of it. Examples: (1) There are no integers with $14m+21n=1$: assume there are, then $7(2m+3n)=1$, so $2m+3n=\frac17$, which is not an integer. (2) $\log_23$ is irrational: assume $\log_23=\frac{p}{q}$ with positive integers, so $2^p=3^q$, which is even equals odd. (3) $x^2-y^2=2$ has no integer solutions: $(x-y)(x+y)=2$, and the factors have the same parity, so both are even and the product is a multiple of 4, not 2.

You may use the fact that $\sqrt2$ is irrational to prove other numbers irrational. To show $\sqrt2+\sqrt3$ is irrational, assume $\sqrt2+\sqrt3=r$ with $r$ rational. Then $\sqrt3=r-\sqrt2$; squaring gives $3=r^2-2r\sqrt2+2$, so $\sqrt2=\frac{r^2-1}{2r}$. The right-hand side is rational, which contradicts the irrationality of $\sqrt2$. Rational numbers are closed under addition, subtraction, multiplication and division by a non-zero number, so combining rationals gives a rational. Isolate a root, square, and arrange so that a known irrational equals a rational expression.

Layout: 'Assume that ... (the negation)'; then each step with a reason; then 'This contradicts ...'; finally 'Hence ... is true'. Do not skip the conclusion. Do not test examples: a few numerical cases never prove a general statement. A contradiction can be with the assumption itself, with a given fact, or with a basic truth such as 'even = odd'. If you reach something that is merely unlikely, it is not a contradiction.