I'm trying to see whether
i) The predicate "$x$ is a multiple of $y$" decidable? If it is, then how can we give a program which computes the characteristic function.
So, for above, I can show it is computable by the following:
$qt(y,x)$ = quotient when $x$ is divided by $y$. Since $qt(y,x+1) = qt(y,x) + 1$ if $rm(y,x) + 1 = x$
and $qt(y,x+1) = qt(y,x)$ if $rm(y,x) +1$ $\ne x$.
We have the following definition by recursion from computable functions:
$qt(0,0) = 0$
$qt(y,x+1) = qt(y,x) + sg(|x-(rm(y,x)+1)|)$
but I need help in translating it to a program. I am not sure if the step of writing it as a computable function is a first good attempt
ii) Do you think "$x$ is prime" is decidable?