Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 6 / a / ii / Solution

The divisibility binary relation on positive natural numbers is not a Euclidean relation. With $x=1$, $y=2$, $z=3$, we have $1\mid 2$ and $1\mid 3$ but $2\nmid 3$. Therefore