Suppose $a$ and $b$ are integers, not both zero. Prove that $a$ and $b$ are relatively prime if and only if there are integers $x, y$ such that $ax + by = 1$.
I know this Bezout's Identity and I saw another question that showed two proofs (one by induction). But I still don't understand them, and I was hoping someone could break them down even further.
My first attempt was:
Proof:
Suppose $a$ and $b$ are relatively prime. The $\gcd(a,b)=d$
therefore $d \mid a$ and $d \mid b$
so $a=dm$ and $b=dk$ for some integers $m, k$
$a+b=dm+dk$
$a+b=dl$ for some integer $l$ by closure
and then I don't know where to go. Eventually I wanted to get to (a,b)=1 because they are relatively prime and tie that into what I had above.
Best Answer
Suppose that $a$ and $b$ are integers. We want to prove that $\gcd(a,b)=1$ if and only if there exists integers $x$ and $y$ verifying $ax+by=1$.
We are going to start by proving the $\Leftarrow$ which is the easiest.
Assume you have a common positive divisor $d$ of $a$ and $b$.
$d$ divides $ax$ and $ay$ and by extension $ax+by$. Meaning $d$ divides $1$, $d=1$ (remember we assumed it to be positive so it can't be equal to $-1$)
The previous line of reasoning proves that there is only one common postive divisor of $a$ and $b$ which is 1. Hence, $\gcd(a, b)=1$.
Now time for the $\Rightarrow$.
We are going to consider the set of nonzero positive linear combination with integer coefficients, take the smallest element and prove it equal to 1.
Namely, $$A=\left\{ax+by |x,y \in \mathbb{Z}\text{ and }ax+by>0 \right \}$$
This set is nonempty. You can prove this by choosing (x,y) as one of these (depending on $a$, $b$ signs) : $$(±1,0), (0,±1)$$
The set $A$ is a subset of $\mathbb{N^*}$.
Ergo, we assert the existence of a smallest element $d=\min A$.
By definition, we can find $x_0,y_0$ integers such that $$\begin{equation} ax_0+by_0=d \tag{*} \label{eq:*} \end{equation} $$
If we prove that $d$ divides both $a$ and $b$, then $d=1$ (because $1$ is the gcd). So let's do that:
Suppose $d$ does not divide $a$, by Euclidean Division theorem we can find an interger $q$ and positive non zero integer $d$ such that: $$a = dq + r$$ $$0<r<d$$ Using $\eqref{eq:*}$, we find $$r =a - q(ax_0+by_0)=(1-qx_0)a+b\times (-y_0)$$
This contradicts the minimality of d, and thus we conclude that $d$ divides $a$. By similar logic we can prove that $d$ divides $b$.
And we find our desired formla, $$ax_0+by_0=1$$
This is my first post in math stack exchange, so excuse the novice layout :(