I have worked out two cases based on negative values, for checking my understanding of the subject.
The theorem is stated to have the variables used being clear. Although, the derivation of gcd or that part is not shown.
Statement : Suppose $a,b \in \mathbb{Z}$, s.t. both $a,b \ne 0$ (i.e. at
least one of them is non-zero), then there exists a unique integer $c$ that
satisfies the condition $c \gt 0, c \mid a, c \mid b$, & $\exists x,y \in
\mathbb{Z}, c = ax + by$ is the smallest positive linear combination.
Special cases based on the above :
As $a,b$ can be positive, negative, or (but not both) zero. So, to have $c$ as a
positive smallest integer for negative $a$,or $b$; entails having at least one of $x,y$ being negative, as shown by examples below.
(The reason why these cases are considered is that for the purpose of finding the smallest positive linear combination, finding the $\gcd$ (by Euclidean algorithm) is the shortest route, and later need to consider sign for the coefficients ($x,y$).)
(i) $a=-3, b= -5, \implies$ finding $c = \gcd(3,5) = 1$, with Bezout's
coefficients given by : $x'=2, y' = 1$. For finding $c$ (as linear combination), with signs considered of $a,b$; the coefficients are : $x=-2, y=1$
(ii) $a = -3, b = 5,
\implies$ finding $c =\gcd(3,5) = 1$, with Bezout's coefficients given by : $x'=2, y' = 1$. For finding $c$ (as linear combination), with signs considered of $a,b$; the coefficients are : $x=-2, y=-1$
There is a positive linear combination of $a$ and $b$; for instance, using $x=a$ and $y=b$ we have $$ xa+yb=a^2+b^2>0 $$ By the properties of the natural numbers, there is the minimum positive linear combination, call it $c$. In particular $c=xa+yb$ for some $x$ and $y$.
Now write $a=cq+r$, with $0\le r<c$. Then $$ r=a-cq=(1-xq)a+(-yq)b $$ Since $r$ is a linear combination of $a$ and $b$ and is less than $c$, it cannot be positive, by minimality of $c$. Therefore $r=0$ and $c\mid a$.
Similarly, $c\mid b$.
Clearly, when $a$ and $b$ are both positive, one among $x$ and $y$, where $c=xa+yb$, must be negative. For instance $a=2$ and $b=3$, we can take $x=-1$ and $y=1$.
However, for $a=-2$ and $b=3$, we can take $x=1$ and $y=1$, but, as well, $x=-2$ and $y=-1$.