Prove that $g(x,y) = \gcd(x,y)$

Question

Define a function $g: \mathbb{N}_0\;\times\;\mathbb{N}_0 \rightarrow \mathbb{N}_0$

Let it have such properties:

1) $g(x,y) = g(y,x)$

2) $g(x,y) = x$, if and only if $y$ is divisible by $x$

3) $g(g(x,y), z) = g(x, g(y,z))$

Prove that $g(x,y) = \gcd(x,y)$

Intuitively I understand that GCD has all these same properties but I guess that it is not enough. In general showing that one function is the same as another one, we must prove that these functions have same value on all possible sets of arguments. Please, show me how to prove such facts in formal way.

Answer 1

If you want to show that some number $N$ is $\gcd(x,y)$ then you need to show two things:

1. $N$ divides $x$ and $y$.

2. If some other number $z$ divides $x$ and $y$ then $z\leq N$.

So you should try to show these two things for $N=g(x,y)$.

For example, we can verify that $g(x,y)$ divides $x$ and $y$. First $g(x,g(x,y))=g(g(x,x),y)$ by (3). So $g(x,g(x,y))=g(x,y)$ by (2). So $g(g(x,y),x)=g(x,y)$ by (1). So $x$ is divisible by $g(x,y)$ by (2). You can do a similar argument to show $g(x,y)$ divides $y$.

So now suppose some other number $z$ divides $x$ and $y$. We want to show $z\leq g(x,y)$. Actually, we'll show $z$ divides $g(x,y)$. By (2) $g(z,x)=z=g(z,y)$. So by (3) we get $g(z,g(x,y))=g(g(z,x),y)=g(z,y)=z$. So $z$ divides $g(x,y)$ by (2).

Answer 2

Hint $\ \color{#c00}{z\mid x}\Rightarrow\, \underbrace{(z,(x,y))}_{\!\!\!\!\textstyle ((\color{#c00}{z,x}),y)} = (\color{#0a0}{z,y})\ $ so $\, \begin{align} \color{#0a0}{z\:\!\mid\:\! y}&\Rightarrow z\mid (x,y)\\ z\!=\!x &\Rightarrow (x,y)\mid x\\[.2em] \end{align}\,$ so $\ \underbrace{\bbox[5px,border:1px solid #c00]{z\mid x,y\iff z\mid (x,y)}_{\phantom{1_1}}\!\!\!\!\!}_{\textstyle\text{i.e. $(x,y)$ is a gcd of $x,y$}_{\phantom{1_1}}\!\!\!\!}$
Remark $\,\ (x,y)\mid x\Rightarrow\,(x,y)\mid y\,$ by symmetry and commutativity. In more detail:
$\quad\,{\begin{align} \!z\mid \color{#0a0}x,\color{#c00}y\Rightarrow\ &(z,(x,y))\overset{3} = ((z,\color{#0a0}x),y)\overset{2} = \overbrace{(z,\color{#c00}y)}^{\textstyle z}\,\overset{2}\Rightarrow\, z\mid (x,y)\\[.5em] z\!=\!x\, \ \ \ \Rightarrow\ &\! (x,(x,y)) = ((x,x),y) = (x,y)\underset{2,\,1}\Rightarrow\, (x,y)\mid x,[\![\:\!y\ \ \text{too by symmetry}\,]\!]\\[,2em] \end{align}}$