RELPRIME
Einfache Sprache
RELPRIME ist das Entscheidungsproblem ob zwei Zahlen teilerfremd sind.
Def. RELPRIME
Gegeben $x,y\in\mathbb N$. Sind $x$ und $y$ relativ prim? Es ergibt sich folgende Sprache
$$\mathrm{RELPRIME} = \{\langle x,y\rangle\mid \text{$x$ und $y$ sind relativ prim}\}$$