1
$\begingroup$

Let $x,y \geq 2 $. Actually I have to show that $CD(x,y)$ is primitive recursive, where $ C(x,y) = 1$ if $gcd(x,y)=1$, otherwise $CD(x,y) = 0$. But I have showed that it is enough to show that $gcd(x,y)$ is primitive recursive.

Which functions are allowed?

1) constant function

2)projection

3) $s(n) = n+1$

4) $\mbox{add}(x,y)$

5) $\mbox{mult}(x,y)$

6) $\mbox{sub}(x,y)$

7) $x^y$

8) $\mbox{sg}(x)$

9) absolute value

10) $\mbox{fac}(x) := x!$

11) $ \mod(N,m) := N \mod m$

12) $ \max(x_1,...,x_m) := \max${$x_1,...,x_m$} for an arbitrary $m$, but fixed.

My idea:

It has something has to do with $11)$ and $12)$, I think. But remember $m$ in $12)$ has to be fixed. My first attempt: $ gcd(x,y) = \max$ { $d \in$ {$0,...,x$}$ | \mod(x,d) = 0 , \mod(y,d) = 0$ }

$\endgroup$
1
$\begingroup$

Hint: The basic relation you need is divisibility: $$D = \{(x,y)\in{\Bbb N}_0^2\mid x\;\text{divides}\; y\}.$$

$x$ divides $y$ if and only if $x·i = y$ for some $1 ≤ i ≤ y$. So the characteristic function of $D$ can be written as $$\chi_D(x, y) = \text{sgn}[\chi_=(x · 1, y) + \chi_=(x · 2, y) + . . . + \chi_=(x · y, y)],$$ where $\chi_=$ is the (primitive recursive) characteristic function of the equality relation $\{(x,x)\mid x\in{\Bbb N}_0\}$. Since the characteristic function $\chi_D$ is primitive recursive, the relation D is primitive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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