Prove each of these statements from each other $\exists x, y: ax +by = 1$ and $\exists u,v: au = bv + 1 $

Question

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.

Answer 1

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.