Relative primality is primitive recursive
Two numbers $x,y$ are not relatively prime iff there exists some common factor $a &gt; 1$, which divides both $x$ and $y$. This common factor can be bounded by $a$. Therefore $x,y$ are not relatively prime iff there exist $a,b \leq x$ and $c \leq y$ such that (i) $a \geq 2$, (ii) $x = ab$, and (iii) $y = ac$.