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)$?
Best Answer
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.