Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 2

up vote 1 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.