Note, that the following functions are primitive recursive
- the (characteristic function of the) equality predicate $\mathrm{Eq} (x,y) = \begin{cases} 1, &\text{if }x = y \\ 0, &\text{if }x \neq y; \end{cases}$
- usual multiplication of natural numbers.
Note, also, that if $f(x,\vec{u})$ is a primitive recursive function, then so is the function $y \mapsto \sum_{x\leq y} f(x,\vec{u})$.
Using this we can define the divisibility predicate by $d ( x , y ) = \textstyle{\sum_{z \leq x}} \mathrm{Eq} ( y \cdot z , x ).$ (In actual fact, this equation is not that cryptic. Note that if $\chi(y,\vec{x})$ is the characteristic function of some predicate, then $\sum_{y \leq z} \chi(y,\vec{x})$ will be positive iff $\chi(y,\vec{x}) = 1$ for some $y \leq z$, and so $\min \{ 1 , \sum_{y \leq z} \chi(y,\vec{x}) \}$ will be the characteristic function for the predicate "$(\exists y \leq z) ( \chi(y,\vec{x}))$." Since given $x,y$ there is at most one $z \leq x$ such that $y \cdot z = x$, we can dispense with the "$\min$" in this specific case. The right-hand-side of the formula above can then be read as the characteristic function of the predicate "$( \exists z \leq x ) ( y \cdot z = x )$" which is exactly what we mean by "$x$ is divisible by $y$.")