записать предикат, показать примитивную рекурсивность

[Marischa]

0 - если НОД(x,y) больше одного и 1 - если НОД(x,y) = 1

[Maslov]

Таким образом, характеристическую функцию Вашего предиката можно записать как
$f(x,y) = 2 \mathop{\overset{\boldsymbol\cdot}{\smash-\vrule width 0pt height 1pt}} dv(x, y)$,
где $\mathop{\overset{\boldsymbol\cdot}{\smash-\vrule width 0pt height 1pt}}$ - операция усеченной разности, а $dv(x, y)$ = НОД(x, y).

Ну а теперь осталось только открыть книгу Р.Петер и разобраться с тем, как можно посчитать $dv(x, y)$. Там же можно посмотреть, что такое усеченная разность.

[Marischa]

Спасибо, попробую дальше разобраться.