Proof by reductio ad absurdum (from Latin words meaning "reducing to an absurdity") is an interesting and useful technique. Put very simply, it works like this:

1. Make an assumption.
2. Deduce an absurdity (a contradiction) from the assumption.

If you can do this, then the assumption must be false (which means that its logical negation must be true).

The easiest example to understand is perhaps the proof that the square root of 2 is irrational. The proof goes like this:

Suppose that the square root of 2 (which we can write as 2^1/2) is rational. If so, then there are two integers, m and n, such that m / n = 2^1/2

But m and n might have some common factors (or they might not). If we cancel all common factors, then we end up with two new integers, p and q, such that p / q = 2^1/2

p might equal m, in which case q will equal n, but it no longer matters at this stage. The important points are that p / q = 2^1/2 and that p and q have no common factors, because they were produced as a result of eliminating all common factors.

(You will find it helpful to bear in mind that the product of two even numbers is always an even number, whereas the product of two odd numbers is always an odd number.)

The proof proceeds quickly:

p / q = 2^1/2

Square both sides:

p² / q² = 2

Multiply both sides by q²:

p² = 2q²

Therefore p² is even, and so p must be even.

Since p is even, there must exist a number r such that 2r = p. Substituting this into the above equation, we get:

(2r)² = 2q²

Therefore:

4r² = 2q²

Dividing both sides by 2 gives:

2r² = q²

Therefore q² is even, and it follows that q must be even too. So we have shown that both p and q are even; i.e. they have 2 as a common factor. And yet we eliminated all the common factors right at the beginning! Since p and q cannot both share a common factor and be co-prime (i.e. share no common factor), we have deduced an absurdity. Therefore, we must conclude that the numbers p and q cannot exist -- that is, there are no two integers whose ratio is the square root of 2. In other words, the square root of 2 is irrational.

Here's another simple example of reductio ad absurdum, which Euclid used to prove the infinitude of primes. We can interpret "the infinitude of primes" as meaning that, if we have a finite set of primes, there is at least one prime that is not in our list.

So let us start by assuming the opposite: i.e. that we have a finite set of primes, and that there are no primes that are not in the list. We proceed to calculate an integer N by multiplying all these primes together, and then adding 1 to the result.

Now, we know that N > 1 (because 2 is prime, so the result has to be at least 2). We also know that dividing N by any of our primes will yield a remainder of 1, so it isn't a multiple of any known prime.

Therefore, either we have a new prime number N, or N is divisible by some other prime that is not in our list. Either way, our list is incomplete.

(Adding the new prime to the list doesn't help, because we can just go round again. And again. And again...)

Thus, no matter how large a finite set of primes we have, we can always prove that there is a prime that is not in the set, and therefore there are infinitely many primes.