Primitive recursive definition of the "divisibility" relation Let $$d(x,y)=
\begin{cases}
1, &\text{if }x\text{ is divisible by }y \\
0, &\text{otherwise.}
\end{cases}$$
How can I define $d(x,y)$ in terms of just the basic primitive recursive functions (zero, successor, identity, projection) and the composition and primitive recursive operations?
 A: The natural approach would be to define the modulus function
$$ m(0,y) = 0 $$
$$ m(x+1,y) = \begin{cases} 0 & \text{if }m(x,y)+1= y \\ m(x,y)+1 &\text{otherwise}\end{cases}$$
Then $d$ is simply
$$ d(x,y) = \begin{cases} 1 &\text{if }m(y,x)=0 \\ 0 &\text{otherwise}\end{cases}$$
So everything will be easy if you can express
$$ f(a,b,x,y) = \begin{cases} a & \text{if }x=y \\ b & \text{otherwise} \end{cases} $$
Do you have some components that might be useful for that? For example if you have the restricted subtraction function $(x,y)\mapsto \max(0,x-y)$, you can build $|x-y|$ from that, and then implement $f$ by primitive recursion over the value of $|x-y|$...
A: 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$.")
