Nobody seems to have bitten on this. The first thing you need to know is that n is a square iff d(n) is odd (and "odd" is easily definable with only addition). So now we have a predicate "IsSquare(n)". The next step is to determine what n is the square of. This is easy - look for the next larger number that is a square. If n = k^2, the next square is k^2+2k+1, so k is half of one less than the distance to the next square. This lets us define the square function. And now n*m (with n>=m) = (square(n+m) - square(n-m))/4. And having defined multiplication, we're done. Franklin T. Adams-Watters -----Original Message----- From: franktaw@netscape.net Since nobody seems to have responded to this, I thought I'd give a hint: Think squares. Franklin T. Adams-Watters -----Original Message----- From: franktaw@netscape.net It is well known that the first-order theory of the non-negative integers with only addition available is decideable, while the theory with addition and multiplication is not. Suppose we have addition and the number of divisors function (often called d(n) or tau(n)). Is the theory then decideable or not? Proof requested. Franklin T. Adams-Watters