Number theory and NP-complete What are some of the natural number theory problems that are np-complete? I am looking for examples not in lattices and geometric number theory. Examples in analytic/algebraic number theory are ok.
 A: See pages 249-251 of Garey and Johnson, Computers and Intractability, for a dozen NP-complete 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
of $j$ for which $c$ divides $b_j$? 
A: 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", "NP-complete decision problems for quadratic polynomials", "Diophantine complexity"), and the references therein. 
One example of the problems they show to be NP-complete is the following decision problem. 


*

*Input: three natural numbers $a,b,c$ (in base $2$), 

*Output: YES/NO depending whether the equation $ax^2 + by = c$ has solutions (for $x,y$) in the natural numbers.
