What's with Bezout's Identity?

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

Solution 1:

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.

Solution 2:

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.

Solution 3:

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:

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.

Solution 4:

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