10
$\begingroup$

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$
  • 6
    $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Aug 15 '16 at 14:19
  • 2
    $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Aug 15 '16 at 14:21
  • $\begingroup$ 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. $\endgroup$ – user307169 Aug 15 '16 at 14:36
  • 2
    $\begingroup$ "if" is not the same as "iff". $\endgroup$ – user21820 Aug 15 '16 at 15:36
12
$\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 "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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user3002473 Aug 15 '16 at 14:28
  • $\begingroup$ @user3002473 It's not a solution. $\endgroup$ – Slade Aug 15 '16 at 14:30
  • 1
    $\begingroup$ 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. $\endgroup$ – florence Aug 15 '16 at 14:30
  • $\begingroup$ @Slade my mistake, I wrote $17$ instead of $19$. $\endgroup$ – user3002473 Aug 15 '16 at 14:31
  • 1
    $\begingroup$ @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. $\endgroup$ – Thomas Andrews Aug 15 '16 at 14:32
3
$\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.

| cite | improve this answer | |
$\endgroup$
2
$\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:

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\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$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.