What's with the definition of Bezout's Identity? As I understand it, it states that if $d = \gcd(a, b)$, then there exist integers $x,\ y$ such that $ax+by=d$.
Why the requirement that $d=\gcd(a,b)$ though? It seems to work even when this isn't the case. For example, let $a = 17$ and $b = 4$. Then $d = 1$, however setting $d = 2$ still generates an infinite number of solutions: $$ x = -4n-2,\quad\quad y=17n+9\\ n\in\Bbb{Z} $$ and for $(a,\ b,\ d) = (19,\ 17,\ 5)$ we get $x=-17n-6$ and $y=19n+7$. However for $(a,\ b,\ d) = (44,\ 55,\ 12)$ we do have no solutions.
So what's the fuss? Why require $d=\gcd(a,b)$? Is it like, you can't guarantee the existence of solutions to $ax+by=d$ unless $d=\gcd(a,b)$, and I just stumbled across a case where it happens to work? In that case can we classify all the cases where there are solutions $x,\ y$, more specifically than just $d=\gcd(a,b)$?
$\endgroup$ 45 Answers
$\begingroup$Say we know that there are solutions to $ax+by=\gcd(a,b)$; then if $k$ is an integer, there are obviously solutions to $ax+by=k\gcd(a,b)$. Just take a solution to the first equation, and multiply it by $k$. In this manner, if $d\neq \gcd(a,b)$, the equation can be "reduced" to one in which $d=\gcd(a,b)$. In your example, we have $\gcd(a,b)=1,k=2$. However, the number on the right hand side must be a multiple of $\gcd(a,b)$; otherwise, there will be no solutions, as $\gcd(a,b)$ clearly divides the left hand side of the equation.
$\endgroup$ 5 $\begingroup$Bézout's identity says that if $a,b$ are integers, there exists integers $x,y$ so that $ax+by=\gcd(a,b)$.
This does not mean that $ax+by=d$ does not have solutions when $d\neq \gcd(a,b)$.
It is obvious that $ax+by$ is always divisible by $\gcd(a,b)$. So this means that $\gcd(a,b)$ is the smallest possible positive integer which a solution exists. It is not at all obvious, however, that we can always achieve this possible solution, which is the crux of Bézout.
$\endgroup$ $\begingroup$The significance is that $d = \gcd(a,b)$ is among the value of $d$ for which there are solutions. This is a significant property that a domain might have — so much so that there is even a special name for them: Bézout domains.
An example where this doesn't happen is the ring of polynomials in two variables $s$ and $t$. $\gcd(st, s^2+st) = s$, but the equation $stx + (s^2+st)y = s$ has no solutions for $(x,y)$.
The complete set of $d$ for which the equation $ax+by=d$ has a solution is $d = k \gcd(a,b)$, where $k$ ranges over all integers. i.e. the set of all linear combinations of $\{a,b\}$ is the same as the set of all linear combinations of $\{ \gcd(a,b) \}$ (a linear combination of one object is just its set of multiples).
This idea generalizes; working with linear combinations of ring elements (with coefficients taken from the ring) is incredibly important in abstract algebra: we call such things ideals, and today we usually start studying them right from the very beginning of ring theory.
Incidentally, if you want a parametrization of all possible solutions, then:
$\endgroup$ $\begingroup$If $ax_0 + by_0 = \gcd(a,b)$, then every solution of $ax+by=d$ for $(x,y)$ is of the form $$ x = \frac{d x_0 + b n}{\gcd(a,b)}$$ $$ y = \frac{d y_0 - a n}{\gcd(a,b)}$$ where $n$ ranges over all integers.
A common definition of $\gcd(a,b)$ is it's a generator of the ideal $(a,b)=\{ma+nb\mid m,n\in \mathbf Z\}$. This is the only definition which easily generalises to P.I.D.s
Such equation do not always have solutions: $\; 6x+9y=$, for instance,have no solution. Actually, it's not hard to prove that, in general $$\{ax+by\mid x,y\in \mathbf Z\}$$ is the set of multiples of $\gcd(a,b)$.
$\endgroup$ $\begingroup$Paraphrasing your final question, we can get to the crux of the matter:
Can we classify all the integer solutions $x,y,z$ to $ax + by = z$, instead of just noting that there exist solutions when $z=\gcd(a,b)$?
Yes. That's the point of the theorem! There's nothing interesting about finding isolated solutions $(x,y,z)$ to $ax + by = z$. If you wanted those, you could just plug in random $x$ and $y$ values and set $z$ to whatever comes out on the other side. The interesting thing is to find all possible solutions to this equation. And it turns out that proving the existence of a solution when $z=\gcd(a,b)$ is the hard part of answering that question. Once you know that, the answer to the original, interesting question is easy:
Corollary of Bezout's Identity. $ax + by = z$ has an integer solution $x,y,z$ if and only if $z$ is a multiple of $d=\gcd(a,b)$.
Proof: First let's show that there's a solution if $z$ is a multiple of $d$. By Bezout's Identity, $ax + by = z$ has a solution if $z=d$, and it's easy to see that a solution exists for any multiple $z = kd$: just take one of those solutions $ax + by = d$ and multiply on both sides by $k$: $$k(ax + by) = kd$$ $$a(kx) + b(ky) = z.$$
Now let's do the other direction: show that whenever there is a solution, then $z$ is a multiple of $d$. By the definition of gcd, there exist integers $m, n$ such that $a = md$ and $b = nd$, so $$z = mdx + ndy = d(mx + ny).$$ We see that $z$ is a multiple of $d$ as advertised. $\square$
$\endgroup$
