Prove each of these statements from each other $\exists x, y: ax +by = 1$ and $\exists u,v: au = bv + 1 $ Hello I am trying to prove the following:
We have show that two numbers a and b are relatively prime if and only if some integer linear combination of them equals 1, that is, if:
 $$\exists x, y: ax +by = 1$$ 
where x and y range over the integers,
and $$\exists u,v: au = bv + 1 $$
where u and v range over the naturals. Prove each of these two statements from each other.
How would I go about this? I decided that I would start by trying to prove the second statement from the first. I started off by instantiating two variables in the first statement for some integer f and g and isolating the ax term:
$$ ∃x,y:ax+by=1 $$
$$ a(f) + b(g) = 1 \space for \space integers \space f \space and \space g $$ 
$$ a(f) = 1 - b(g)$$
I do not know how to continue on after this point. 
 A: This is an exercise in elementary transformations, and possibly working backward.
Suppose $x,y$ are such that $ax+by = 1$. 
Without loss of generality, we assume that $y$ is negative (otherwise, we can make it so, since $a(x+nb) +b(y-na) = 1 $ for all natural numbers $n$, so just choose $n$ large enough and put $x := x +nb$ and $y := y - na$), in which case $x$ is positive (leaving out trivial cases).
Let $u = x , v= - y$. Then, $ax + by = au-bv = 1 \implies au = bv+1$.
Similarly, if $au=bv+1$, then putting $x=u$ and $y=-v$ gives $ax+by=1$ for some integers $x,y$ (here, $y$ will be negative).

EDIT : 
For the first part, we have to assume that there exist integers $x,y$ such that $ax+by = 1$. From this, we have to show the existence of $u,v$ natural numbers such that $au = bv+1$.
So we have assumed that $x,y$ exist. I want to now ensure, that $y$ is negative. How do I do this? Let us take an example to clarify.
Let $a=5, b=3$. You can check for yourself, that with $x=-1, y=2$, we get that $ax+by = -5 + 6 = 1$. How do I ensure that $y$ is negative? Here's how:
Let $n$ be any fixed natural number (what it is, we shall decide later). Note that:
$$
1 = (ax + by) = (ax + anb) + (by - anb) = a(x+nb) + b(y-na) 
$$
The crux of this transformation is the following:

Given one pair of numbers $x,y$ satisfying $ax+by=1$, we can generate infinitely many pairs of numbers $c=x+nb,d=y-na$ such that $ac+bd=1$, since the parameter $n$ can vary over all natural numbers.

In our case, $a=5,b=3$, so we can write:
$$
1 = 5(-1+3n) + 3(2-5n)
$$
Suppose we put $n=1$, then we get $1 = 5(2) + 3(-3)$. If we write this as $ax+by=1$, then we see that $x$ is positive, and $y$ is negative. 
From here, everything I have said should work out.
Please clarify if doubts persist.
