To build upon the "Just relax" section: by Shoenfield's absoluteness theorem[1], if ZFC proves some Sigma^1_3 statement, then ZF also proves it. In particular, the Axiom of Choice has no arithmetic consequences, and thus has no effect on number theory, nor what you are able to prove about the correctness of any particular algorithm, etc.

[1] https://en.wikipedia.org/wiki/Absoluteness#Shoenfield's_abso...