Remainder function being arithmetic I am reading Kleene's "Introduction to Metamathematics" chapter 9 section 48, where he mentions that "We know that the predicate $rm(c,d)=w$, where $w$ is the remainder when $c$ is divided by $d$, is arithmetical" (1971 ed. pp.239). I know that $rm(c,d)=w$ is primitive recursive but I have trouble understanding why it is arithmetical. I would like to understand this without using the result that all primitive recursive functions are arithmetical. Definition: Predicate is arithmetical if it can be expressed explicitly in terms of constant, variable natural numbers, functions $+$, $\cdot$, equality $=$, the operations "implies", "and", "or", "not", and the quantifiers "for all", "there exists", combined according to the usual syntactical rules. I would appreciate your help!

As indicated by fleablood in the comments, we can write the relation $rm(c,d)=w$ as $$ w