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:


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

  • $\begingroup$ 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. $\endgroup$ – Janik Sep 27 '16 at 20:29
  • $\begingroup$ @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. $\endgroup$ – ntgoodatmth Sep 27 '16 at 20:33
  • $\begingroup$ 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. $\endgroup$ – 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 $$\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$$ $$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 :(

  • $\begingroup$ 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}. $\endgroup$ – 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.

  • $\begingroup$ excuse me for being the worse at number theory but for the second part, are you proving that by contradiction as well? $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.