I'm not so sure that we're missing anything basic. The top rated answer by Scott Aaronson seems spot on to me. The natural numbers are just too powerful. As the resolution of Hilbert's tenth problem shows, we can at best hope to solve special cases of statements involving natural numbers, and the solvable cases are bound to require techniques of increasing complexity.

What would count as a "master theorem" for some field, anyway? I suppose something like Tarski's quantifier elimination of semialgebraic sets over R^n might be an example, though for actual computations the best algorithms have double exponential worst case complexity (i.e. even worse than integer factorization). Or for something even more basic, perhaps the fundamental theorem of linear algebra (along with Gaussian elimination). There's the saying that mathematics is the art of reducing any problem to linear algebra -- I suppose the hard problems in number theory are the ones that don't have a good linear algebra reformulation :-)