What are some of the natural number theory problems that are npcomplete? I am looking for examples not in lattices and geometric number theory. Examples in analytic/algebraic number theory are ok.
You can take a look at the papers by Adleman and Manders (not always in this order) from the 70s (at least "Computational complexity of decision procedures for polynomials", "NPcomplete decision problems for quadratic polynomials", "Diophantine complexity"), and the references therein. One example of the problems they show to be NPcomplete is the following decision problem.



See pages 249251 of Garey and Johnson, Computers and Intractability, for a dozen NPcomplete problems in Number Theory. EDIT: A couple of examples, by request. AN2, Simultaneous incongruences. Given a collection $\lbrace(a_1,b_1),\dots,(a_n,b_n)\rbrace$ of ordered pairs of positive integers with $a_i\le b_i$ for $1\le i\le n$, is there an integer $x$ such that for all $i$, $x\not\equiv a_i\pmod{b_i}$? AN4, Comparative divisibility. Given sequences $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_m$ of positive integers, is there a positive integer $c$ such that the number of $i$ for which $c$ divides $a_i$ is more than the number 

