# How to test if a polynomial GCD is correct

I'm studying the Zippel algorithm for computing multivariate polynomial GCDs, which is probabilistic in the sense that it uses some random numbers, and assumes that if a polynomial coefficient is zero, then it is actually zero (as opposed to only zero at the randomly chosen values).

In [Zi79], the author makes the following claim:

Since the results for GCD and factorization can be checked by division, one is guaranteed to obtain the correct answer, if need be, by performing the calculation twice.

I can certainly see how we can check if a polynomial is a common divisor, but how can we be sure it is a greatest common division?

I just don't understand how "results for GCD... can be checked by division".

Can anybody help me?

[Zi79] Richard Zippel, PROBABILISTIC ALGORITHMS FOR SPARSE POLYNOMIALS, Laboratory for Computer Science, Massachusetts Institute of Technology

If $$d$$ divides both $$a$$ and $$b$$, then $$d=\gcd(a.b)$$ iff $$\gcd ({a\over d}, {b\over d})=1.$$