Proof by contradiction
In the previous chapter we considered how to construct some simple direct proofs. However, the direct method can be inconvenient and does not always work. In this chapter we consider a logically more elaborate but very common and powerful method of proof: proof by contradiction.
The direct method of proof is often hard to use when we are proving negative statements. Consider the following example.
Proposition 4.1.1 There do not exist integers m and n such that
14m + 20n = 101.
This is a simple example of a non-existence result and results of this type are very common in more advanced mathematics.
It is difficult to see how to prove Proposition 4.1.1 directly for we clearly ...