The Euclidean Algorithm and the Linear Diophantine Equation ax + by = gcd( a , b )

In this note, we prove that for any positive integers a and b, with dD gcd.a; b/, among all integral solutions to the equation axC byD d, the solution.x0; y0/ that is provided by the Euclidean algorithm lies nearest to the origin. In fact, we prove that.x0; y0/ lies in the interior of the circle centered at the origin with radius 1 2d p a2C b2.