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

http://mathoverflow.net/questions/264201/the-strength-of-saying-each-sentence-of-true-arithmetic-has-a-recursive-proof

Here's a statement: **every integer $n \in \mathbb{Z}\backslash\{0\}$ 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?