Euclid's theorem that there is an infinity of prime numbers has multiple proofs, ranging from the original Euclid theorem that constructs a new prime number from a finite list of such numbers, to the proof of Euler which requires the theory of products and infinite sums. The latter is clearly ingenious, but excessive, while the former is elegant, simple and often an example of proof for people with little knowledge of mathematics (for example, students, readers of popular math books).

I am curious to know which fragment of arithmetic is necessary to perform the Euclid's proof, or otherwise, if there is an even lower limit on the logical force of the theorem.