Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Calculus, linear algebra, discrete mathematics, logic and proof, and models of computation / 8 / c / Solution

Here the direction of the divisibility relation matters: $R(x,z)$ means $z\mid x$. The first two clauses say that $z$ is a common divisor of $x,y$. The last clause says that every common divisor $w$ divides $z$. These are precisely the defining properties of the greatest common divisor. Choose $z=\gcd (x,y)$; thenHenceThis also holds if the natural numbers include zero: use $\gcd (x,0)=x$ and $\gcd (0,0)=0$. Every natural number divides zero, so for $x=y=z=0$ the last clause remains true. In the order obtained by reversing divisibility, the greatest common divisor is the least upper bound.