Euclid's theorem that there are infinitely many prime numbers has multiple proofs, ranging from Euclid's original theorem that constructs a new prime from a finite list of such, to Euler's proof that requires the theory of infinite products and sums. The latter is clearly ingenious, but overkill, whereas the former is elegant, simple, and often shown as an example of a proof to people with little mathematical background (eg students, readers of popular mathematics books).

I'm curious to know what fragment of arithmetic is needed to perform Euclid's proof, or otherwise, if there is an even lower bound on the logical strength of the theorem.

Provability of the Pigeonhole Principle and the Existence of Infinitely Many Primes. This is already quite weak, and has been further weakened more recently, but it’s an open question whether bounded arithmetic on its own would suffice. $\endgroup$12more comments