I have worked out a case based on negative values, for checking my understanding of the subject. Please vet it.
Have stated the proof to show the variables used, so as to link to the actual example.
Proof: In the derivation of the proof (by contradiction) that (given, $\gcd =c$) $c \mid a$, the division algorithm is considered.
$\exists t,u \in \mathbb{Z}, s.t.: a = ct + u, 0 \le u \lt c.$
Hence, $a = ct +u = axt + byt +u$
=> $u = a(1-xt) + b(-yt)$.
As $c$ is smallest positive linear combination hence c $\le$ a, b.
By definition, $u \lt c$, & a linear combination of $a,b$.
As, $c$ is the smallest such combination; so: $u = 0$.
==> Question: It seems that $|c| \le |a|,|b|$. So, is it the positive value of $a,b$ that needs be taken for comparison with $c$. Also, by defn., $c = \gcd$, so $c$ must be positive.
The special case here is based on negative values of either $a$ or $b$.
It is given: $u = a(1-xt) + b(-yt)$,
Now, to numerically state that : $u$ is smaller than $c$, need state :
$$a(1-xt) + b(-yt) \lt ax + by$$
=> $a \lt ax(1+t) + by(1+t)$.
1. Let, $a = -3, b= -5; c = 1; x = -2, y = 1$
Finding the value of t, by substituting values in the above inequality:
$-3 \lt -3\cdot-2(1+t) -5\cdot1\cdot(1+t)$
$-3 \lt (1+t)$
$t \gt -4$
Taking the smallest value of $t= -3$
=> $u = a(1-xt) + b(-yt)$
=> $u = -3(1+3x) -5(3y)$
=> $u = 15 -15 = 0$
Any higher value of $t$ leads to a negative value of $u$, but as $u$ cannot be less than $0$, so only one value of $t$ is acceptable.
2. Let, $a = -3, b= 5; c = 1; x = -2, y = -1$
Finding the value of t, by substituting values in the above inequality:
$-3 \lt -3\cdot-2(1+t) -5\cdot(1+t)$
$-3 \lt (1+t)$
$t \gt -4$
Taking the smallest value of $t= -3$
=> $u = a(1-xt) + b(-yt)$
=> $u = -3(1+3x) + 5(3y)$
=> $u = -3(1-6) + 5(-3)$
=> $u = 0$
Any higher value of $t$ leads to a negative value of $u$, but as $u$ cannot be less than $0$, so only one value of $t$ is acceptable.
3. Considering now positive values of $a,b$, with $a = 3, b= 5, c = 1, x = 2, y = -1$
Finding the value of t, by substituting values in the above inequality:
$3 \lt +3\cdot2(1+t) -5\cdot(1+t)$
$3 \lt (1+t)$
$2 \lt t$
$t \gt 2$
Taking the smallest value of $t= 3$
=> $u = a(1-xt) + b(-yt)$
=> $u = 3(1-6) + 5(3)$
=> $u = 0$
Any higher value of $t$ leads to a negative value of $u$, but as $u$ cannot be less than $0$, so only one value of $t$ is acceptable.
As euclidean division is used, hence a unique value of quotient and remainder is there, and this gels with only one value of $t$ in each case.