Euclid's proof of the infinitude of primes
[? How does Euclid prove it ?
 Does he use contradiction? I think he doesn't...]

mentioned here b/c often distorted
\begin{proof}
Given a finite set of primes $p_1,\dots,p_k$,
consider $p_1\dotsm p_k+1$.
This is relatively prime to the existing set,
so its prime factorization contains a further prime.
\end{proof}

The bad proof starts:
``By contradiction. Assume on the contrary that there is a finite set.'',
then include the above proof,
then concludes
``But this contradicts our assumption!''
This is how false contradictions go.
(oh, oops: it's not a naive contraposition)

It feels like a proper contradiction,
b/c it involves a construction,
which seems to use a negation of the conclusion.
...but the subtle point is that *you don't need to assume that
this finite set is *all* the primes*!


It's also often stated as a case analysis:
- this new number is either prime,
- or is divisible and has a new prime factor
...but these are subsumed by taking the prime factorization.
[is this too strong?
 Yes -- oops. Actually, good commentary:
 we don't need to use the full strength of prime factorization,
   (and Euclidean algorithm)
 just that you're either prime or composite.]
