Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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
Thanks, I had already checked out the wikipedia page. –  Ryan Nov 11 '12 at 21:44
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
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.

share|improve this answer
Thanks Arthur. I will save your answer for when I reach the "characteristic function" part of my course material. :) –  Ryan Nov 11 '12 at 19:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.