# The $\gcd(a,b)$ can be expressed of the form $ax+by$, such that: $\gcd(a,b)=ax+by$, if $x$ and $y$ are integers are they unique?

Its is my assumption that they are not unique although am yet to find an arguement to prove this

-
Your first impulse, when thinking that something might be so, should be to try out a simple example. Like $a=2$ and $b=5$. Then see whether the single equation $2x+5y=1$ has a unique solution in integers. Examples should come before everything else in gaining understanding. – Lubin Feb 19 '13 at 21:46

Let $d=\gcd(a,b)$. Let $a=da'$ and $b=db'$.

Suppose that $ax_0+by_0=d$. Then the solutions of $ax+by=d$ are given by $$x=x_0-tb',\qquad y=y_0+ta',$$ where $t$ ranges over the integers.

Remark: It is easy to verify that these are solutions, since $(a)(-tb')+(b)(ta')=0$.

To prove that there are no others, suppose that $ax+by=d$. Then by subtraction we find that $a(x-x_0)+b(y-y_0)=0$, and therefore $a'(x-x_0)=-b'(y-y_0)$. Since $a'$ and $b'$ are relatively prime, we conclude that $a'$ divides $y-y_0$. Let $y-y_0=ta'$. Then $y=y_0+ta'$. It follows that $x=x_0-tb'$.

-

Hint $\$ Like any linear equation, if the associated homogeneous equation has nonzero solutions then the solutions to the non-homogeneous equation are not unique. This applies here since its homogenous form $\rm\ A\, X = (a,b)\cdot (x,y) = ax + by = 0\$ has obvious solution $\rm\,X = (-b,a).$

Generally, for $\rm A\:$ linear, $\rm\ A\,X_1\! = B = A\,X_2 \ \iff\ 0 \:=\: A\,X_1\! - A\,X_2 = A\,(X_1\!-X_2)$

This implies that the general solution of $\rm\,\ A\,X = B\,\$ is the sum of any fixed particular solution plus any solution of the associated homogeneous equation $\rm\ A\,X = 0.\:$ This property holds true for every linear operator, e.g. for matrices, linear differential equations, linear recurrences, etc, a fact which will come to the fore if you study linear algebra and vector/affine spaces, modules, etc.

-

Uniqueness is dismissed by simply observing that $$(a+y)x+(b-x)y=ax+by.$$

-
I like this answer best because it is nice and short and answers exactly the question posed. – Tara B Feb 19 '13 at 22:49