# 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.

• If you suppose that $a$ and $b$ are relatively prime, then $gcd(a,b)=1$ (per definition). I really don't understand why you wrote $d$ in that case. – Janik Sep 27 '16 at 20:29
• @Masacroso if I do it by contradiction, can I technically keep the argument I have now. I am still not sure where to go with the contradiction. – ntgoodatmth Sep 27 '16 at 20:33
• You can definitely do a proof by contradiction: $ax + by = dmx + dky=d(mx+ky)$. If $a$ and $b$ are not relatively prime $d \ne 1$ and that doesn't equal one. Therefore: if ax + by = 1 => a and b are relatively prime. That's half your proof the other way is harder. – fleablood Sep 27 '16 at 21:30

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 $\Leftarrow$.

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 \}$$

1. 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)$$

2. 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 $$$$ax_0+by_0=d \tag{*} \label{eq:*}$$$$

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$$ $$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 the same logic on $b$, you 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 :(

• The layout is excellent as the first post from a new user. It's ok to have 1 line without MathJax $$ax_0+bx_0 = 1.\tag{**}\label1$$ However, if you have variables $x,y$ and numbers $1$ on the same line, it's better to wrap them with dollar sign, like $1$ and $x,y$ for consistency. (Optional:) to cite equation \eqref{1}, you may use \eqref{1}. If you don't like the brackets, you may add a star: \tag*{}. $$\therefore ax_0+bx_0 = 1.\tag*{\square}\label2$$ To cite equation \ref{2} without brackets, you may take away eq: \ref{2}. – GNUSupporter 8964民主女神 地下教會 Jan 27 '18 at 13:17

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.

• excuse me for being the worse at number theory but for the second part, are you proving that by contradiction as well? – ntgoodatmth Sep 27 '16 at 21:05

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)$.

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.

• I would be glad if someone comment the downvote or correct me if Im wrong, thank you. – Masacroso Oct 2 '16 at 20:40