  We study interactions between Skolem Arithmetic and certain classes of
Constraint Satisfaction Problems (CSPs). We revisit results of Glass er et al.
in the context of CSPs and settle the major open question from that paper,
finding a certain satisfaction problem on circuits to be decidable. This we
prove using the decidability of Skolem Arithmetic. We continue by studying
first-order expansions of Skolem Arithmetic without constants, (N;*), where *
indicates multiplication, as CSPs. We find already here a rich landscape of
problems with non-trivial instances that are in P as well as those that are
NP-complete.
