Prove that if a and b are positive integers, then there exists integers x and y such that 1/lcm(a,b)=x/a+y/b

Question

My professor has not taught us the technique of writing proofs, he just continues to do them for us in class. So I am really stumped on this proof.

Any help is greatly appreciated!

Answer 1

By a standard theorem often called Bézout's Identity, there exist integers $x$ and $y$ such that $$bx+ay=\gcd(a,b).\tag{1}$$ Recall that $$\gcd(a,b)\operatorname{lcm}(a,b)=ab.\tag{2}$$ (This is a reasonable thing to use, since (1) involves the gcd, but the result we are trying to prove involves the lcm.) So by (1) and (2) there exist integers $x$ and $y$ such that $$bx+ay=\frac{ab}{\operatorname{lcm}(a,b)}.$$ Divide both sides by $ab$.

Answer 2

There's no single technique of writing proofs. It's a skill you learn only by doing and reading many examples.

So you want to prove there exist integers $x$,$y$ such that

$$ \frac{1}{lcm(a,b)} = \frac{x}{a} + \frac{y}{b}.$$

This expression looks a little complicated and not too meaningful, so maybe we can simplify it. Let's cross multiply the right hand side, maybe it'll make more sense.

$$\frac{1}{lcm(a,b)} = \frac{bx+ay}{ab}.$$

This is a little better, but still not very helpful. But I notice $ab$ on one side and $lcm(a,b)$ on the other side and I know these two expressions are related, so I multiply out by $ab$ to get:

$$\frac{ab}{lcm(a,b)} = bx+ ay.$$

Notice everything I've done is reversible, so I've only rephrased the problem. Now the above equation looks a bit more meaningful to me. That's because I know $ab = gcd(a,b).lcm(a,b)$ so $ab/lcm(a,b) = gcd(a,b)$. That means the equation which I'm trying to show has solutions is equivalent to

$$ gcd(a,b) = bx + ay.$$

Now the question has been reduced to something well-known. It's a standard fact from elementary number theory about the gcd that the above equation has a solution. So if we accept this as fact, we have solved the problem. Now to write up a formal proof we might be very concise and work backwards:

Given $a$ and $b$, we know there exist $x$,$y$ such that $bx + ay = gcd(a,b)$. We also have $gcd(a,b)lcm(a,b) = ab$, therefore:

$$ bx+ay = \frac{ab}{lcm(a,b)} \Longrightarrow \frac{bx+ay}{ab} = \frac{1}{lcm(a,b)},$$

and so

$$ \frac{1}{lcm(a,b)} = \frac{bx}{ab} + \frac{ay}{ab} = \frac{x}{a} + \frac{y}{b}.$$

And we are done. Notice the way we started thinking about this problem ran the opposite way of how we wrote the proof. Most of the time when a proof appears to magically solve the problem this is what's really going on.