The theory of integer multiplication with order restricted to primes is decidable
Françoise Maurin · Journal of Symbolic Logic · 1997
Abstract We show here that the first order theory of the positive integers equipped with multiplication remains decidable when one adds to the language the usual order restricted to the prime numbers. We see moreover that the complexity of the latter theory is a tower of exponentials, of height O(n).