# Show that the greatest common divisor $gcd(x,y)$ is primitive recursive.

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

## 1 Answer

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.