A Euclidean algorithm takes any two integers m,n and finds $$d=\gcd(m,n)$$ It also finds integers $a,b$ such that $$am+bn=d$$
Q: Does the Euclidean Algorithm always find the minimum $a,b$? That is, is it possible for
$$\exists a^\prime,b^\prime \in Z \ni a^\prime m+b^\prime n=d, \\ \left \lVert a' \right \rVert+ \left \lVert b' \right \rVert < \left \lVert a \right \rVert+ \left \lVert b \right \rVert $$
The identity that you are referring to, $$am + bn = d$$ Is knows as Bezout's identity
If we know one pair of Beout's coeffiecients $(a, b)$, then the others $(a', b')$ are in general of the form
$$ a' = a + \frac{kn}{d} \\ b' = b - \frac{km}{d} \\ \text{where} \ k\in \mathbb{Z} $$
Let's check that $a', b'$ actually satisfy the identity:
$$ a'm + b'n = \left(a + \frac{kn}{d}\right)m + \left(b - \frac{km}{d} \right)n \\ = am + \frac{kmn}{d} +bn -\frac{kmn}{d} \\ = am + bn \\ = d $$
Cool, it looks like they do. Hence,
$$ a'm + b'n = d \ \ \ \forall a', b' $$
However, notice that
$$ \left|a' \right| + \left|b'\right| = \left| a + \frac{kn}{d}\right| + \left| b -\frac{km}{d} \right| \\ = |a| + |b| + \left|k \left[ \frac{n}{d} - \frac{m}{d} \right] \right|, k \in \mathbb{Z} $$
Since
$$ \left(\delta = \left|k \left[ \frac{n}{d} - \frac{m}{d} \right] \right| \right) >= 0, $$
$$a' + b' \geq a + b$$
and is equal when $\delta = 0$