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