You can prove it by using mathematic induction.
let P(n) be the following proposition:
if the integer a is in [-nb,-(n-1)b), then there exist integer q and r, such that a=qb+r, where 0=< r < b.
The intuitive idea is that you take this negative and start adding to it ( must be positive). By adding as many time as needed (call it times) you will come to the neighborhood of 0. If you hit 0 directly, then . If you don't hit 0 directly, then after some step you'll be at , and the next step at . So, since is negative, .
Induction is just a formal way to explain the phrase "By adding b as many time as needed".
Like you said theorem states that if f(t) & g(t) are polynomials then such that f(t)=q(t)g(t)+r(t), where . I just wrote it more clearly.
So, I would prove the Euclidean algorithm in a slightly different way. If or if , then we have the required representation . Now suppose , say and where & .
So we form the polynomial:
Actually, this is the first step in long division.
Then . By induction, there exists polynomials q_1 (t) and r(t) such that where neither or .
Putting this into the above and solving for f(t):
Which is the representation we wanted.