Suppose a and b are integers, not both zero. Prove that $a$ and $b$ are relatively prime if and only if exists integers $x, y$ such that $ax + by = 1$ 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. 
 A: 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 :(
A: You got confused at the start; I am guessing you started off meaning to assume $a$ and $b$ were not relatively prime (and that is where the $d$ came in.
Let's start that way, to prove the "if" part -- that is, $a$ and $b$ are relatively prime if there are integers $x,y$ such that $ax+by=1$:
Suppose $a$ and $b$ are not relatively prime. Then $(a,b) = d > 1$ (by definition of "relatively prime" and $a=Ad, b=Bd$ for some integers $A$ and $B$ (by definition of "$d$ divides $a$ and $b$).  Then 
$$
ax + by = Axd + Byd = (Ax+bY) d \neq 1
$$
since $d >1$ and for no integer $z$ do we have $zd = 1$ if $d>1$.  So if for some integer $x,y$ we have $ax + by = 1$, then by contradiction we have shown that $(a,b)=1$.
Next, we prove the "only if" part:  Assume then by Bezout's identity we can find $x,y$ such that  $ax + by = 1$.
That second part was too easy -- maybe what we wanted to do was prove Bezout.  
A: HINT: You can write and iff statement in this way
$$(A\iff B)\iff (A\land B)\lor (\lnot A\land \lnot B)$$
Or you can prove first an implication $(A \implies B)$ and after the other $(A \impliedby B)$.
And then for implications you can try to prove by the contrapositive:
$$(A\implies B)\iff (\lnot B\implies \lnot A)$$
It is important to know that
$$\lnot(\exists x: A)\iff(\nexists x: A)\iff(\forall x:\lnot A)$$
Then if we symbolize co-primality by $\gcd(a,b)=1$ then we can try
$$\begin{align}&\gcd(a,b)=1\implies \exists x,y\in\Bbb Z: ax+by=1\iff
\\&\nexists x,y\in\Bbb Z: ax+by=1\implies \gcd(a,b)\neq 1\iff\\&\color{red}{\forall x,y\in\Bbb Z: ax+by\neq1\implies \gcd(a,b)\neq 1}\end{align}$$  
and in the other direction
$$\begin{align}&\gcd(a,b)=1\impliedby \exists x,y\in\Bbb Z: ax+by=1\iff
\\&\nexists x,y\in\Bbb Z: ax+by=1\impliedby \gcd(a,b)\neq 1\\&\color{red}{\forall x,y\in\Bbb Z: ax+by\neq1\impliedby \gcd(a,b)\neq 1}\end{align}$$
I think the marked in red are easier to prove.
A: Let $I$ be the minimal ideal containing both ideals $I_a$ and $I_b$, the ideals generated by $a$ and $b$ respectively. Every ideal that contains $I_a$ and $I_b$ has the property that every element $d$ satisfies $d = 0 \mod c$ for every common divisor $c$ of $a$ and $b$. So $I$ is generated by $gcd(a,b)$.
