Tricky well defined function and induction Lets define a function $f$ such that $\Bbb N \times\Bbb N \to\Bbb N$.
It takes two natural numbers as inputs and also outputs a natural number.
Let $f$ have the following properties

*

*$f(a,b) = f(b,a)$ for all $a$ and $b$ in natural numbers

*$f(a,0) = a$ for all $a$ in natural numbers

*$f(a,b) = f(a-b,b)$ for all $a$ and $b$, when $a \ge b$ and $b \gt 0$
Now, I need to prove two things about $f$

Q1. Why is $f$ no longer well defined if we replace property 3 with $f(a,b) = f(a-b,a)$ for $a\ge b$ and $b > 0$?
Q2.  Prove by induction that there exist integers $x$ and $y$ in natural numbers such that $xa + yb = f(a,b)$.

For Q1, i figured that if $a\ne b$, and both $a$ and $b \ne 0$ and $a>b$
then $f(a,b) = f(a-b,a)$
now we know $a-b < a$, but from property 1, $f(a-b,a) = f(a,a-b)$
and since $a> a-b$,
$f(a, a-b) = f(a-a+b,a)$ which simplifies to $f(b,a)$ from property 3. then $f(b,a) = f(a,b)$
Now we can see the chain here as $f(a,b) = f(a-b,a) = f(a,a-b) = f(b,a)$
Can I argue that this function will never resolve for some $a$ and $b$ values, therefore its not well defined?
Im really not sure how to handle Q2. Which variables do I induct on?
 A: You’ve spotted where the problem lies in the first question, but you’ve not actually demonstrated that $f$ isn’t well-defined. To do that, you must show that there are (at least) two different functions from $\Bbb N\times\Bbb N\to\Bbb N$ that satisfy conditions $1,2$, and $3'$, where $3'$ is the modified third condition. See if you can show that the functions $\gcd(a,b)$ and $\max\{a,b\}$ both satisfy conditions $1,2$, and $3'$.
For the second question you want a double induction. Let $P(b)$ be the statement that for each $a\ge b$ there are $x,y\in\Bbb Z$ such that $ax+by=f(a,b)$; you want to prove by induction on $b$ that $P(b)$ is true for all $b\in\Bbb N$. For the induction step assume that $P(b')$ is true for $0\le b'<b$, and use this induction hypothesis to prove $P(b)$ by induction on $a$, with a base case $a=b$.
A: I'm not sure how to prove your question if it must be proved by induction, but here is a rough outline of a proof without.
Inspired by the Euclidean Algorithm, we write for any pair of integers $a,b$,
$$a=q_0b+r_0$$
$$b=q_1r_0+r_1$$
$$r_0=q_2r_1+r_2$$
$$r_1=q_3r_2+r_3$$
and so on. This process must terminate at some n to give
$$r_n=q_{n+2}r_{n+1}+0$$
where $r_{n+1}$ is the greatest common divisor of $a,b$.
Then we can write 
$$f(a,b)=f(a-b,b)=...=f(r_0,b)=f(b,r_0)$$
$$f(b,r_0)=f(b-r_0,r_0)=...=f(r_1,r_0)=f(r_0,r_1)$$
$$f(r_0,r_1)=...=f(r_1,r_2)$$
$$...$$
$$...=f(r_n, r_{n+1})=f(r_{n+1},0)=r_{n+1}=\gcd(a,b)$$
Now from Bezout's Identity, then there exist integers $x$ and $y$ such that $ax+by=\gcd(a,b)=f(a,b)$, and this completes our proof
