*a*and

*b*are in the field and

*b*is not zero, than there always exists an element of the field,

*c*, such that

*a = bc.*

So, division is easy, just "push it" over the field, like division in base, or multi precision division.

Algorithm, Knuth "The Art Computer Programming Vol 4" and the others:

# input: coefficients of polynomials as a lists u, v != 0 # in order u[0] = free coefficient of u(x), .... # returns polynomials q, r such that u = vq + r(rest) # length u >= length v >= 0 def poly_divide(u, v): m = len(u) - 1 n = len(v) - 1 q = [0] * (m - n + 1) lim = m - n for k in range(lim, -1, -1): q[k] = u[n + k] / v[n] for j in range(n + k - 1, k - 1, -1): u[j] = u[j] - q[k] * v[j - k] return q, u[:n]

Having division, we can compute the Great Common Divisor, showing, that Euclidean Domain is larger than expected:

def poly_gcd(u, v): if not any(v): return u else: return poly_gcd(v, poly_mod(u, v))

*poly_mod*it's just a rest returned from division algorithm. I think it's beautiful, don't you?

The code, as usually on github , (division.py). Thank you, see you next time!