Wednesday 21 February 2018

elementary number theory - Does the Extended Euclidean Algorithm always return the smallest coefficients of Bézout's identity?

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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...