I found a routine for the Gcd, but not for
the division. Did I miss something?

no, you are not missing anything, the routine 'EuclideanQuotient' was not
ready before the final deadline.

The following routine should work for polynomials over fields:

-----------------------------------------------------------------------------
EuclideanQuotient := function ( f, g )
    local   m,  n,  i,  k,  c,  q,  R,  val;

# <f> and <g> must have the same field
if f.baseRing <> g.baseRing  then
    Error( "<f> and <g> must have the same base ring" );
fi;

# and they must be ordinary polynomials
if f.valuation < 0 then
Error( "<f> must not be a laurent polynomial" );
fi;
if g.valuation < 0 then
Error( "<g> must not be a laurent polynomial" );
fi;
R := f.baseRing;

# if <g> is zero signal an error
if 0 = Length(g.coefficients)  then
    Error( "<g> must not be zero" );
fi;

# if <f> is zero return it
if 0 = Length(f.coefficients) then
return f;
fi;

# remove the valuation of <f> and <g>
f := ShiftedCoeffs( f.coefficients, f.valuation );
g := ShiftedCoeffs( g.coefficients, g.valuation );

# Try to divide <f> by <g>
q := [];
n := Length(g);
m := Length(f) - n;
for i  in [ 0 .. m ]  do
    c := f[m-i+n] / g[n];
    for k  in [ 1 .. n ]  do
        f[m-i+k] := f[m-i+k] - c * g[k];
    od;
    q[m-i+1] := c;
od;

# return the polynomial
return Polynomial( R, q, 0 );

end;
-----------------------------------------------------------------------------

best wishes
Frank Celler