the euclidean algorithm doesn't restrict x,y to be positive. x and y can very well be negative.

the number of solutions of ax+by=c areinfiniteif gcd(a,b) divides c. if (x1, y1) is any particular solution then (x1+[b/d]t, y1-[a/d]t) is also a solution for any integer 't'.