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!