I don't fully understand this other question, but there's a clear relationship between logic and number theory

the strength of saying "each sentence of true arithmetic has a recursive proof"

Here's a statement: every integer $n \in \mathbb{Z}$ has a unique prime factorization which could be thought of as defining a tree structure on the integers.

For a theoretical computer scientist this is just like any other tree, which can be iterated through or breadth-first search or DFS, etc. The fact that the nodes are integers is almost immaterial.

All I know is that certain number theory statements could be be proven with first order logic and others with second order logic, but I doubt anyone details which logic structures were actually used.

Even more basic, does the Euclidean algorithm define a recursive structure on pairs of integers or sequence of integers?