[tjgq]

In my humble opinion, proofs by contradiction are not the best examples of mathematical reasoning to be presented to the uninitiated. It has been my experience that people untrained in mathematics find it difficult to (intuitively) accept them as valid.

[phaemon]

Euclid's proof isn't a proof by contradiction. As the wikipedia page says:

>"Euclid is often erroneously reported to have proved this result by contradiction"

It simply says that if you are constructing a list of primes, you can always add one more to the list, therefore there are infinitely many.

[tjgq]

The overall structure of the proof is not by contradiction, but one of the steps is. The Wikipedia article calls this out, right after the sentence you quoted.

[lutusp]

Also, even though it's correct that Euclid didn't pose it as a proof by contradiction, it can certainly be posed that way, and I often use that form when presenting it to nonmathematicians.

[tjgq]

Not everyone thinks the same way. There are certainly lay persons out there who do not find proofs by contradiction jarring when they come across them for the first time. I remember I was one of them.

But the impression I get from my (possibly biased) sample is that most non-trained people intuitively see proof by contradiction (or any form of nonconstructive proof, really) as a way of "cheating", because it asserts something does or does not exist without actually producing a (counter)example. YMMV, of course.