I know that if $a$ and $b$ have a highest common factor $h$ then you can write $h=ax+by$ for some $x,y \in \mathbb{Z}$ but how about if you can write $h=ax+by$ for some $x,y \in \mathbb{Z}$ then can you write $h=\gcd(a,b)$?
I.e. Is $h=\gcd(a,b) \iff h=ax+by,~ x,y \in \mathbb{Z}$
$\endgroup$ 24 Answers
$\begingroup$What you ask is not quite true, but something related is true.
Let $a,b$ be integers with highest common factor (more commonly called greatest common divisor) $d$ then the set $\{x a + y b\colon x, y \in \mathbb{Z} \}$ is exactly the same as $\{zd \colon z \in \mathbb{Z}\}$ so the set of multiples of $d$.
So, if you can write something as $ax + by$ you at least know it is divisible by the highest common factor, or put the other way round the highest common factor must divide that number. Especially, when you can write $1$ in this way you know the highest common factor is $1$ (as $1$ has no positive divisor other than $1$).
$\endgroup$ 2 $\begingroup$General Bezout Identity $\,\ h = ax\! +\! by\,$ for some $\,x,y\in\Bbb Z \iff d\!:=\!(a,b)\mid h$
Proof $\ \ (\Rightarrow)\ \ $ If $\ h = \color{#c00}ax\!+\!\color{#c00}by\ $ then $\,d\mid \color{#c00}{a,b}\,\Rightarrow\, d\mid h$
$(\Leftarrow)\ \ $ If $\,d\mid h \,$ then $\,h = kd\ $ for $\,k\in\Bbb Z.\,$ By Bezout there are $\,m,n\in\Bbb Z\,$ such that
$$\ d\!=\!(a,b) = a m\! +\! b n \ \overset{\times\ k}\Rightarrow\, h \,=\, a (km) + b(kn)\quad{\bf QED} $$
Remark $ $ Said more succinctly in ideal or group language it is simply
$$ \bbox[8px,border:1px solid #c00]{a\,\Bbb Z + b\, \Bbb Z\, =\, (a,b)\,\Bbb Z}\qquad\qquad\qquad$$
$\endgroup$ 2 $\begingroup$My first answer handled the case of coprime integers (I misread the question).
To answer your question, the other way of course doesn't work, there are a lot of counter examples you can find easily:
3 - 1 = 2; 5 + 3 = 8; 10 - 7 = 3; etc.
$\endgroup$ $\begingroup$What you can say is that if you can write $h=ax+by$ and if $h$ is a (positive) common factor of $a$ and $b$, then $h=\gcd(a,b)$.
$\endgroup$
