Bezout's identity says that there are integers $x$ and $y$ such that $ax + by = gcd(a, b)$ and the Extended Euclidean Algorithm finds a particular solution. For instance,
$333\cdot-83 + 1728\cdot16 = \gcd(333, 1728) = 9$.
Will the Extended Euclidean Algorithm always return the smallest $x$ and $y$ that satisfy the identity? By small, I mean that $|x|, |y|$ are minimized.
Because $333\cdot(-83 + 1728t) + 1728\cdot(16 - 333t) = \gcd(333, 1728)$ is also a solution for all $t \in \mathbf{Z}$.
No comments:
Post a Comment