# How to define divisibility recursively?

Let $d(x,y)=1$ if $x$ is divisible by $y$, and $=0$ otherwise.

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?

Thank you.

-
Review Link: Have you looked at common-primitive-recursive-functions? You'll find an elaborations of the basic primitive functions you refer to, and how, from those, we can obtain limited subtraction...and so forth. The link will take you to some primitive function, including division, but if you scroll to the top, and read from the start, it may shed some insight on how to define divisibility using more primitive functions as "building blocks". –  amWhy Nov 11 '12 at 20:32
I just moved the link & my answer to the "comment" section below your question, and removed it from my answer (since deleted). I simply wanted you to have quick access to it if you want to revisit the post/site in the future. You just get automatically notified if someone "comments" or answers your question. –  amWhy Nov 11 '12 at 22:13

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|$...

-
Oh yes I do have the modified difference function you refer to, but I haven't been able to figure out how to build $d$ from this function. Can you give a hint perhaps? –  Ryan Nov 11 '12 at 18:15
@Ryan: That's what I describe in the answer! –  Henning Makholm Nov 11 '12 at 18:20
@Ryan: Nobody says $d$ itself needs to be defined directly by primitive recursion. In the definition I propose in my answer, it is constructed by composition: $d(x,y)=f(1,0,m(y,x),0)$. –  Henning Makholm Nov 11 '12 at 18:38
@Ryan: Are you reading my answer at all? It (and my previous comment) tells you exactly what to compose. And yes, you do need define some auxiliary functions -- thougn not necessarily the modulus function if you go with Arthur's hint instead. –  Henning Makholm Nov 11 '12 at 19:00
I understand your solution, but I don't understand how your solution relates to your suggestion to bring in the restricted subtraction/absolute diff functon. I have found out from wikipedia that mod is listed as a common PR function, but because it hasn't been introduced in my course, I am not allowed to use it as a building block (unless of course I separately show that mod is PR). –  Ryan Nov 11 '12 at 19:08
Hint: Let $\mathrm{Eq}$ denote the characteristic function of the equality predicate ($\mathrm{Eq} (x,y) = 0$ if $x \neq y$; $\mathrm{Eq} (x,x) = 1$). Then $$d ( x , y ) = \textstyle{\sum_{z \leq y}} \mathrm{Eq} ( x \cdot z , y ).$$ So all you need to do is show that $\mathrm{Eq}$, multiplication, and bounded sums of primitive recursive functions are primitive recursive.