What is the simplest number-theoretic theorem whose proof requires exponentiation or finite sequences/sets (so any proof in Peano Arithmetic would need to use encodings of such things using e.g. Gödel's beta function) but the statement of the theorem itself does not require them?
By "simple" I mean that the proof is simple, not just that the statement of the theorem is simple. Therefore, e.g. the Green-Tao theorem does not count.
The example I have in mind is the following: "Let $p$ be an odd prime. Then $-1$ is a quadratic residue modulo $p$ if and only if $p\equiv 1 \pmod 4$." The proof I know uses Euler's criterion, which involves exponentiation (and the proof I know of Euler's criterion uses, among other things, Wilson's theorem which involves factorials).