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

• Well, you obviously need $\gcd(a,b)$ to be a divisor of $d$. But the "fuss" is that you can always solve for the case $d=\gcd(a,b)$, and for no smaller positive $d$. – Thomas Andrews Aug 15 '16 at 14:19
• Bezout doesn't say you can't have solutions for other $d$, in any event. Clearly, if $ax+by=d$ then $a(xz)+b(yz)=dz$. – Thomas Andrews Aug 15 '16 at 14:21
• Posting this as a comment because there's already a sufficient answer. Here's a specific counterexample. Let $a = 10$ and $b = 5$. Then $\gcd(a,b) = 5$. Let $d = 2\ne \gcd(a,b)$. Then $ax + by = d$ becomes $10x + 5y = 2$. This is equivalent to $2x+y = \dfrac25$, which clearly has no integer solutions. – user307169 Aug 15 '16 at 14:36
• "if" is not the same as "iff". – user21820 Aug 15 '16 at 15:36

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 "reduces" 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.

• Ok so if I understand correctly, since Bezout's identity states $19x + 4y = 1$ has solutions, then $19(2x)+4(2y)=2$ clearly has solutions as well. Meaning $19x+4y=2$ has solutions, but $x$ and $y$ are both even. If that's true, then why is $(x,y)=(-6,29)$ a solution to $19x+4y=2$? How does Bezout's identity explain that? – user3002473 Aug 15 '16 at 14:28
• @user3002473 It's not a solution. – Slade Aug 15 '16 at 14:30
• Since $4$ is already even, you could just rewrite the equation as $19(2x)+4y=2$ if you want a more general solution set. You can easily reason that the first unknown number has to be even, here. – florence Aug 15 '16 at 14:30
• @Slade my mistake, I wrote $17$ instead of $19$. – user3002473 Aug 15 '16 at 14:31
• @user3002473 We didn't say that all solutions to $17x+4y=2$ would have $x,y$ even, just one of the solutions. There is no contradiction. – Thomas Andrews Aug 15 '16 at 14:32

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.

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.

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

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$