# 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

1. $f(a,b) = f(b,a)$ for all $a$ and $b$ in natural numbers
2. $f(a,0) = a$ for all $a$ in natural numbers
3. $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?

-
Q2 is false. I suspect that you’re supposed to prove that for all natural numbers $a$ and $b$ there exist integers $x$ and $y$ such that $xa+yb=f(a,b)$. – Brian M. Scott Mar 5 '13 at 5:21
@user65065: Welcome to MSE! It really helps readability to format question in MathJax. I started your off as an example. Regards – Amzoti Mar 5 '13 at 5:24
Thanks for the suggestion guys, first post so lot to learn – user65065 Mar 5 '13 at 5:28
@BrianM.Scott would it be correct to say that Q2 is probably asking us to prove that $f(a,b)$ is a multiple of $gcd(a,b)$? – Vincent Tjeng Mar 5 '13 at 5:46
@user65065 since your function is defined from the natural numbers to the natural numbers, how can $f(a,0)$ have a value? – Vincent Tjeng Mar 5 '13 at 5:50

## 2 Answers

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$.

-

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

-