Proof by Contradiction revision

I understand that some people say this is the most tricky topic to tackle in A level maths. I think it's because there is no straight forward method to tackle every question the same way, since the questions have their own specific proof. In that case, wouldn't I just need to actually try and go through all these types and try to memorize each specifically. Of course there are similar questions with overlapping proofs...

If you do a lot of these then you will adapt your way of thinking when it comes to a new problem.


No point memorising each one specifically. This is a waste of time.

Memorising infinitude of primes proof is probably the one you should.

Irrationality of rt(2) can be memorised, but what happens if you are required to prove rt(p) is irrational for any prime p?

Alright then thanks. That last one got me stumped tho

It really shouldn't. Here's a proof that sqrt(2) is irrational:


Suppose (for contradiction) $\sqrt{2}$ rational. Then we can write $\sqrt{2}$ as a fraction $\dfrac{a}{b}$ with a, b in lowest terms.

But then $\dfrac{a^2}{b^2} = 2$, so $a^2 = 2b^2$.

Since 2 divides the RHS, we deduce 2 divides the LHS too, and so a = 2N for some N.

But then we have $2^2N^2 = 2b^2$, so $2N^2 = b^2$.

Now 2 divides the LHS, so we deduce 2 divides the RHS, so b = 2M for some M.

But this implies that a, b were not in lowest terms after all! Contradiction.

Now, to prove sqrt(p) is irrational, just take the above proof, and replace 2 by p. (To state the obvious, note that the exponents remain as 2).

Note: I did make sure that I worded the proof in such a way that it was trivial to change to a proof for a general prime p. You might want to compare with the proof that sqrt(2) is irrational that you have in your textbook.

Challenge: To test your understanding, where would this proof break down if p is actually a square. (e.g. if p = 4, there's obviously going to be a problem claiming that sqrt(4) is irrational!).

Thanks for taking the time out to do this, although my confusion was the question "but what happens if you are required to prove rt(p) is irrational for any prime p?" I guess I thought it was a mixture of both the proof of infinite primes and root 2. But yes if p does equal to 4 then it wouldn't work to call it irrational because a/b would just equal to 2 which is a rational number.

It does seem you're confused.

For the first question, I've just told you exactly what you should do. If it's the "for any prime p" part (as opposed to being asked to, say prove that sqrt(7) is irrational), then you just need to start with "Let p be any prime." and then go straight into the proof. (i.e. the next line would start "Suppose (for contradiction) $\sqrt{p}$ rational", and so on...)

For the 2nd question, you're missing the point. We know sqrt(4) is rational. But if I'm just "replacing 2 by p" in the proof (and you'll note the proof doesn't ever obviously use the fact that p is prime), I can just say "p = 4" to get a "proof" that sqrt(4) is irrational. Obviously that proof is invalid. But what I'm challenging you to do is to find out which step in the proof is the one that goes wrong.

Thinking about things like "where does this proof go wrong when I try to adapt it to prove something obviously false?" is important in terms of truly understanding what's going on.

Is it that the proof falls apart in the last part where b and a are both multiples of p therefore p is a rational number and not an irrational one?

We're saying p=4. Rational/irrational doesn't come into it.

If you're stuck: set p=4 and try to break the proof. Choose a and b so you'd expect the proof to fail. (i.e. a = 2, b = 1), and go through step by step until you find a step that's invalid (i.e. it will tell you something about a, b that you know isn't true).

I've lost the plot. What is the point of this and what's the actual question again? Sorry I just can't keep up with you